-
Notifications
You must be signed in to change notification settings - Fork 1
/
driver.cpp
381 lines (328 loc) · 14.9 KB
/
driver.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
/**
* @file driver.cpp
* @author Rogelio Schevenin, Sawyer Thompson
* @redID 824107681, 823687079
* @brief Multi Level Paging with TLB Cache entry point
* @date 2022-03-21
*/
#include <iostream>
#include <stdio.h>
#include <fstream>
#include <string.h>
#include <math.h>
#include <map>
#include <ctype.h>
#include "tracereader.h"
#include "output_mode_helpers.h"
#include "pagetable.h"
#define TOTALPAGEBITSMAX 28
/**
* @brief Main Execution of Multi Level Paging with TLB Cache
*
* @param argc integer amount of arguments
* @param argv character array of arguments
* @return int value indicating exit status
*/
int main(int argc, char **argv)
{
PageTable *pageTable; // instantiate page table
OutputOptionsType *output; // instantiate output object
std::map<uint32_t, uint32_t> TLB; // instantiate map of <VPN, PFN>
std::map<uint32_t, uint32_t> LRU; // instantiate map of <VPN, Access Time>
FILE *tracefile; // instantiate tracefile
uint32_t physicalAddress; // instantiate physical address
uint32_t VPN; // instantiate virtual page number
uint32_t offset; // instantiate offset
uint32_t PFN; // instantiate page frame number
uint32_t newFrame; // instantiate new frame
int pageSize; // instantiate page size
int addressProcessingLimit; // instantiate address limit
int tlbCapacity; // instantiate size of TLB
int lruCapacity; // instantiate size of LRU
int cacheHits; // instantiate cache hits
bool tlbHit; // instantiate TLB is hit
bool ptHit; // instantiate page table is hit
const char *outputType; // instantiate type of output
pageTable = new PageTable(); // initialize page table
output = new OutputOptionsType(); // initialize output object
pageTable->offsetSize = DEFAULTSIZE; // initialize offset size
addressProcessingLimit = DEFAULTADDRLIMIT; // initialize address limit
tlbCapacity = DEFAULTTLBSIZE; // initialize size of TLB
lruCapacity = DEFAULTLRUSIZE; // initialize size of LRU
outputType = DEFAULTOUTPUTTYPE; // initialize output type
// check optional arguments
int opt;
while ((opt = getopt(argc, argv, "n:c:o:")) != -1)
{
switch (opt)
{
// sets number of addresses needed to go through
case 'n':
addressProcessingLimit = atoi(optarg);
// verify address limit is a number
for (int i = 0; optarg[i] != 0; i++)
{
if (!isdigit(optarg[i]))
{
std::cout << "Incorrect address processing limit--should be a number." << std::endl;
exit(EXIT_FAILURE);
}
}
break;
// gets cache capacity of adresses
case 'c':
tlbCapacity = atoi(optarg);
// verify cache input is a number and verify valid cache capacity
for (int i = 0; optarg[i] != 0; i++)
{
if ((!isdigit(optarg[i])) || (tlbCapacity < 0))
{
std::cout << "Cache capacity must be a number, greater than or equal to 0" << std::endl;
exit(EXIT_FAILURE);
}
}
break;
// gets type of output
case 'o':
outputType = optarg;
break;
default:
exit(EXIT_FAILURE);
}
}
// require at least 2 arguments
if (argc - optind < 2)
{
std::cout << "Level 0 page table must be at least 1 bit" << std::endl;
exit(EXIT_FAILURE);
}
// verify working tracefile
tracefile = fopen(argv[optind++], "rb");
if (tracefile == NULL)
{
std::cout << "Unable to open <<" << argv[optind - 1] << ">>" << std::endl;
exit(EXIT_FAILURE);
}
pageTable->numLevels = argc - optind; // get number of levels in page table
pageTable->bitsPerLevel = new uint32_t[pageTable->numLevels]; // create array to store bit count per level
pageTable->bitShiftPerLevel = new uint32_t[pageTable->numLevels]; // create array to store bit shift per level
pageTable->entriesPerLevel = new uint32_t[pageTable->numLevels]; // create array to store entry counts per level
// loop through each page level argument
for (int i = optind; i < argc; i++)
{
// verify valid page size
if (atoi(argv[i]) <= 0)
{
std::cout << "Level " << (i - optind) << " page table must be at least 1 bit" << std::endl;
exit(EXIT_FAILURE);
}
pageTable->bitsPerLevel[i - optind] = atoi(argv[i]); // store bits count for level i
pageTable->entriesPerLevel[i - optind] = pow(2, pageTable->bitsPerLevel[i - optind]); // store entries for level i
pageTable->totalPageBits += atoi(argv[i]); // store total bits
// verify valid bit sizes
if ((pageTable->totalPageBits) > TOTALPAGEBITSMAX)
{
std::cout << "Too many bits used in page tables" << std::endl;
exit(EXIT_FAILURE);
}
pageTable->offsetSize -= (atoi(argv[i])); // offset at level i
pageTable->bitShiftPerLevel[i - optind] = (DEFAULTSIZE - pageTable->totalPageBits); // amount of bit shift at level i
}
pageSize = pow(2, pageTable->offsetSize); // set page size
pageTable->vpnMask = ((1 << pageTable->totalPageBits) - 1) << pageTable->offsetSize; // set vpn mask
pageTable->offsetMask = (1 << pageTable->offsetSize) - 1; // set offset mask
pageTable->pageLookupMask = new uint32_t[pageTable->numLevels]; // array of page lookup masks
pageTable->pageLookup = new uint32_t[pageTable->numLevels]; // array of page lookup masks
// find page lookup masks at each level
for (int i = 0; i < pageTable->numLevels; i++)
{
pageTable->pageLookupMask[i] = ((1 << pageTable->bitsPerLevel[i]) - 1) << (pageTable->bitShiftPerLevel[i]);
}
pageTable->addressCount = 0; // keep track of addresses processed from tracefile
newFrame = 0; // keep track of new frames mapped
cacheHits = 0; // keep track of amount of cache hits
// process each address in tracefile until address limit is reached
while (!feof(tracefile) && pageTable->addressCount != addressProcessingLimit)
{
// next address
p2AddrTr *address_trace = new p2AddrTr(); // instantiate address trace
// if another address exists
if (NextAddress(tracefile, address_trace))
{
pageTable->addressCount++; // increment addresses processed
VPN = virtualAddressToPageNum(address_trace->addr, pageTable->vpnMask, pageTable->offsetSize); // find address VPN
offset = virtualAddressToPageNum(address_trace->addr, pageTable->offsetMask, 0); // find address offset
// set page lookups (indexes) per level
for (int i = 0; i < pageTable->numLevels; i++)
{
pageTable->pageLookup[i] = virtualAddressToPageNum(address_trace->addr, pageTable->pageLookupMask[i], pageTable->bitShiftPerLevel[i]);
}
// found VPN in TLB
if (TLB.find(VPN) != TLB.end() && tlbCapacity > 0)
{
// TLB hit
tlbHit = true;
ptHit = false;
cacheHits += 1;
// PFN from TLB
PFN = TLB[VPN];
// TLB is full and VPN is not in LRU
if ((TLB.size() == tlbCapacity) && (!LRU[VPN]))
{
uint32_t oldestKey; // VPN
uint32_t oldestValue; // access time
oldestValue = pageTable->addressCount; // start with current access time
// find oldest VPN in LRU
for (std::map<uint32_t, uint32_t>::iterator iter = LRU.begin(); iter != LRU.end(); ++iter)
{
// VPN access time exists (not NULL) and is older than last oldest
if ((iter->second) && (iter->second < oldestValue))
{
oldestKey = iter->first; // update oldest VPN
oldestValue = iter->second; // update oldest access time
}
}
// erase oldest VPN in LRU
LRU.erase(oldestKey);
}
// Update VPN access time in LRU
LRU[VPN] = pageTable->addressCount;
}
// not found in TLB
else
{
// TLB miss, walk PageTable
// search PageTable for VPN
Map *found = pageLookup(pageTable, address_trace->addr);
// VPN exists in PageTable
if (found)
{
// TLB miss, PageTable hit
tlbHit = false;
ptHit = true;
pageTable->pageTableHits += 1;
// update associated PFN
PFN = found->frame;
}
// VPN doesn't exist in PageTable
else
{
// TLB miss, PageTable miss
tlbHit = false;
ptHit = false;
// insert vpn and new frame into page table
pageInsert(pageTable, address_trace->addr, newFrame);
// update associated PFN
PFN = newFrame;
}
// if using cache
if (tlbCapacity > 0)
{
uint32_t oldestKey; // oldest VPN
uint32_t oldestValue; // oldest access time
// if TLB is full
if (TLB.size() == tlbCapacity)
{
// TLB size > LRU size
if (tlbCapacity > lruCapacity)
{
// check all LRU items for oldest value
oldestValue = pageTable->addressCount; // start with current access time
for (std::map<uint32_t, uint32_t>::iterator iter = LRU.begin(); iter != LRU.end(); ++iter)
{
// VPN access time exists (not NULL) and is older than last oldest
if ((iter->second) && (iter->second < oldestValue))
{
oldestValue = iter->second;
oldestKey = iter->first;
}
}
}
// TLB size < LRU size
else
{
// check all TLB items for oldest value
oldestValue = pageTable->addressCount; // start with current access time
for (std::map<uint32_t, uint32_t>::iterator iter = TLB.begin(); iter != TLB.end(); ++iter)
{
// if next access time in TLB is older
if (LRU[iter->first] < oldestValue)
{
oldestKey = iter->first;
oldestValue = LRU[iter->first];
}
}
}
// erase oldest VPN from TLB
TLB.erase(oldestKey);
}
// LRU is full and VPN is not in LRU
if ((LRU.size() == lruCapacity) && (!LRU[VPN]))
{
// find oldest VPN in LRU
oldestValue = pageTable->addressCount; // start with current access time
for (std::map<uint32_t, uint32_t>::iterator iter = LRU.begin(); iter != LRU.end(); ++iter)
{
// VPN access time exists (not NULL) and is older than last oldest
if ((iter->second) && (iter->second < oldestValue))
{
oldestKey = iter->first; // update oldest VPN
oldestValue = iter->second; // update oldest access time
}
}
// erase oldest VPN from LRU
LRU.erase(oldestKey);
}
// if VPN found in PageTable
if (ptHit)
{
// insert found VPN->PFN mapping into TLB and LRU
TLB[VPN] = found->frame;
LRU[VPN] = pageTable->addressCount;
}
// if VPN was not found in PageTable
else
{
// insert new VPN->PFN mapping into TLB and LRU
TLB[VPN] = newFrame;
LRU[VPN] = pageTable->addressCount;
}
}
// update new frame counter if PageTable was not hit
if (!ptHit)
{
newFrame++;
}
}
// calculate physical address
physicalAddress = (PFN * pageSize) + offset;
// output that needs to loop
if (strcmp(outputType, "virtual2physical") == 0)
{
report_virtual2physical(address_trace->addr, physicalAddress);
}
if (strcmp(outputType, "vpn2pfn") == 0)
{
report_pagemap(pageTable->numLevels, pageTable->pageLookup, PFN);
}
if (strcmp(outputType, "offset") == 0)
{
fprintf(stdout, "%08X\n", offset);
}
if (strcmp(outputType, "v2p_tlb_pt") == 0)
{
report_v2pUsingTLB_PTwalk(address_trace->addr, physicalAddress, tlbHit, ptHit);
}
}
}
// output that doesn't need to loop
if (strcmp(outputType, "summary") == 0)
{
report_summary(pageSize, cacheHits, pageTable->pageTableHits, pageTable->addressCount, newFrame, countPageTableSize(pageTable, pageTable->rootLevelPtr));
}
if (strcmp(outputType, "bitmasks") == 0)
{
report_bitmasks(pageTable->numLevels, pageTable->pageLookupMask);
}
return 0;
};