1 #include "u.h"
2 #include "../port/lib.h"
3 #include "mem.h"
4 #include "dat.h"
5 #include "fns.h"
6 #include "../port/error.h"
7
8 #define pghash(daddr) palloc.hash[(daddr>>PGSHIFT)&(PGHSIZE-1)]
9
10 struct Palloc palloc;
11
12 void
pageinit(void)13 pageinit(void)
14 {
15 int color, i, j;
16 Page *p;
17 Pallocmem *pm;
18 ulong m, np, k, vkb, pkb;
19
20 np = 0;
21 for(i=0; i<nelem(palloc.mem); i++){
22 pm = &palloc.mem[i];
23 np += pm->npage;
24 }
25 palloc.pages = xalloc(np*sizeof(Page));
26 if(palloc.pages == 0)
27 panic("pageinit");
28
29 color = 0;
30 palloc.head = palloc.pages;
31 p = palloc.head;
32 for(i=0; i<nelem(palloc.mem); i++){
33 pm = &palloc.mem[i];
34 for(j=0; j<pm->npage; j++){
35 p->prev = p-1;
36 p->next = p+1;
37 p->pa = pm->base+j*BY2PG;
38 p->color = color;
39 palloc.freecount++;
40 color = (color+1)%NCOLOR;
41 p++;
42 }
43 }
44 palloc.tail = p - 1;
45 palloc.head->prev = 0;
46 palloc.tail->next = 0;
47
48 palloc.user = p - palloc.pages;
49 pkb = palloc.user*BY2PG/1024;
50 vkb = pkb + (conf.nswap*BY2PG)/1024;
51
52 /* Paging numbers */
53 swapalloc.highwater = (palloc.user*5)/100;
54 swapalloc.headroom = swapalloc.highwater + (swapalloc.highwater/4);
55
56 m = 0;
57 for(i=0; i<nelem(conf.mem); i++)
58 if(conf.mem[i].npage)
59 m += conf.mem[i].npage*BY2PG;
60 k = PGROUND(end - (char*)KTZERO);
61 print("%ldM memory: ", (m+k+1024*1024-1)/(1024*1024));
62 print("%ldM kernel data, ", (m+k-pkb*1024+1024*1024-1)/(1024*1024));
63 print("%ldM user, ", pkb/1024);
64 print("%ldM swap\n", vkb/1024);
65 }
66
67 static void
pageunchain(Page * p)68 pageunchain(Page *p)
69 {
70 if(canlock(&palloc))
71 panic("pageunchain (palloc %p)", &palloc);
72 if(p->prev)
73 p->prev->next = p->next;
74 else
75 palloc.head = p->next;
76 if(p->next)
77 p->next->prev = p->prev;
78 else
79 palloc.tail = p->prev;
80 p->prev = p->next = nil;
81 palloc.freecount--;
82 }
83
84 void
pagechaintail(Page * p)85 pagechaintail(Page *p)
86 {
87 if(canlock(&palloc))
88 panic("pagechaintail");
89 if(palloc.tail) {
90 p->prev = palloc.tail;
91 palloc.tail->next = p;
92 }
93 else {
94 palloc.head = p;
95 p->prev = 0;
96 }
97 palloc.tail = p;
98 p->next = 0;
99 palloc.freecount++;
100 }
101
102 void
pagechainhead(Page * p)103 pagechainhead(Page *p)
104 {
105 if(canlock(&palloc))
106 panic("pagechainhead");
107 if(palloc.head) {
108 p->next = palloc.head;
109 palloc.head->prev = p;
110 }
111 else {
112 palloc.tail = p;
113 p->next = 0;
114 }
115 palloc.head = p;
116 p->prev = 0;
117 palloc.freecount++;
118 }
119
120 Page*
newpage(int clear,Segment ** s,ulong va)121 newpage(int clear, Segment **s, ulong va)
122 {
123 Page *p;
124 KMap *k;
125 uchar ct;
126 int i, hw, dontalloc, color;
127
128 lock(&palloc);
129 color = getpgcolor(va);
130 hw = swapalloc.highwater;
131 for(;;) {
132 if(palloc.freecount > hw)
133 break;
134 if(up->kp && palloc.freecount > 0)
135 break;
136
137 unlock(&palloc);
138 dontalloc = 0;
139 if(s && *s) {
140 qunlock(&((*s)->lk));
141 *s = 0;
142 dontalloc = 1;
143 }
144 qlock(&palloc.pwait); /* Hold memory requesters here */
145
146 while(waserror()) /* Ignore interrupts */
147 ;
148
149 kickpager();
150 tsleep(&palloc.r, ispages, 0, 1000);
151
152 poperror();
153
154 qunlock(&palloc.pwait);
155
156 /*
157 * If called from fault and we lost the segment from
158 * underneath don't waste time allocating and freeing
159 * a page. Fault will call newpage again when it has
160 * reacquired the segment locks
161 */
162 if(dontalloc)
163 return 0;
164
165 lock(&palloc);
166 }
167
168 /* First try for our colour */
169 for(p = palloc.head; p; p = p->next)
170 if(p->color == color)
171 break;
172
173 ct = PG_NOFLUSH;
174 if(p == 0) {
175 p = palloc.head;
176 p->color = color;
177 ct = PG_NEWCOL;
178 }
179
180 pageunchain(p);
181
182 lock(p);
183 if(p->ref != 0)
184 panic("newpage: p->ref %d != 0", p->ref);
185
186 uncachepage(p);
187 p->ref++;
188 p->va = va;
189 p->modref = 0;
190 for(i = 0; i < MAXMACH; i++)
191 p->cachectl[i] = ct;
192 unlock(p);
193 unlock(&palloc);
194
195 if(clear) {
196 k = kmap(p);
197 memset((void*)VA(k), 0, BY2PG);
198 kunmap(k);
199 }
200
201 return p;
202 }
203
204 int
ispages(void *)205 ispages(void*)
206 {
207 return palloc.freecount >= swapalloc.highwater;
208 }
209
210 void
putpage(Page * p)211 putpage(Page *p)
212 {
213 if(onswap(p)) {
214 putswap(p);
215 return;
216 }
217
218 lock(&palloc);
219 lock(p);
220
221 if(p->ref == 0)
222 panic("putpage");
223
224 if(--p->ref > 0) {
225 unlock(p);
226 unlock(&palloc);
227 return;
228 }
229
230 if(p->image && p->image != &swapimage)
231 pagechaintail(p);
232 else
233 pagechainhead(p);
234
235 if(palloc.r.p != 0)
236 wakeup(&palloc.r);
237
238 unlock(p);
239 unlock(&palloc);
240 }
241
242 Page*
auxpage(void)243 auxpage(void)
244 {
245 Page *p;
246
247 lock(&palloc);
248 p = palloc.head;
249 if(palloc.freecount < swapalloc.highwater) {
250 unlock(&palloc);
251 return 0;
252 }
253 pageunchain(p);
254
255 lock(p);
256 if(p->ref != 0)
257 panic("auxpage");
258 p->ref++;
259 uncachepage(p);
260 unlock(p);
261 unlock(&palloc);
262
263 return p;
264 }
265
266 static int dupretries = 15000;
267
268 int
duppage(Page * p)269 duppage(Page *p) /* Always call with p locked */
270 {
271 Page *np;
272 int color;
273 int retries;
274
275 retries = 0;
276 retry:
277
278 if(retries++ > dupretries){
279 print("duppage %d, up %p\n", retries, up);
280 dupretries += 100;
281 if(dupretries > 100000)
282 panic("duppage\n");
283 uncachepage(p);
284 return 1;
285 }
286
287
288 /* don't dup pages with no image */
289 if(p->ref == 0 || p->image == nil || p->image->notext)
290 return 0;
291
292 /*
293 * normal lock ordering is to call
294 * lock(&palloc) before lock(p).
295 * To avoid deadlock, we have to drop
296 * our locks and try again.
297 */
298 if(!canlock(&palloc)){
299 unlock(p);
300 if(up)
301 sched();
302 lock(p);
303 goto retry;
304 }
305
306 /* No freelist cache when memory is very low */
307 if(palloc.freecount < swapalloc.highwater) {
308 unlock(&palloc);
309 uncachepage(p);
310 return 1;
311 }
312
313 color = getpgcolor(p->va);
314 for(np = palloc.head; np; np = np->next)
315 if(np->color == color)
316 break;
317
318 /* No page of the correct color */
319 if(np == 0) {
320 unlock(&palloc);
321 uncachepage(p);
322 return 1;
323 }
324
325 pageunchain(np);
326 pagechaintail(np);
327 /*
328 * XXX - here's a bug? - np is on the freelist but it's not really free.
329 * when we unlock palloc someone else can come in, decide to
330 * use np, and then try to lock it. they succeed after we've
331 * run copypage and cachepage and unlock(np). then what?
332 * they call pageunchain before locking(np), so it's removed
333 * from the freelist, but still in the cache because of
334 * cachepage below. if someone else looks in the cache
335 * before they remove it, the page will have a nonzero ref
336 * once they finally lock(np).
337 */
338 lock(np);
339 unlock(&palloc);
340
341 /* Cache the new version */
342 uncachepage(np);
343 np->va = p->va;
344 np->daddr = p->daddr;
345 copypage(p, np);
346 cachepage(np, p->image);
347 unlock(np);
348 uncachepage(p);
349
350 return 0;
351 }
352
353 void
copypage(Page * f,Page * t)354 copypage(Page *f, Page *t)
355 {
356 KMap *ks, *kd;
357
358 ks = kmap(f);
359 kd = kmap(t);
360 memmove((void*)VA(kd), (void*)VA(ks), BY2PG);
361 kunmap(ks);
362 kunmap(kd);
363 }
364
365 void
uncachepage(Page * p)366 uncachepage(Page *p) /* Always called with a locked page */
367 {
368 Page **l, *f;
369
370 if(p->image == 0)
371 return;
372
373 lock(&palloc.hashlock);
374 l = &pghash(p->daddr);
375 for(f = *l; f; f = f->hash) {
376 if(f == p) {
377 *l = p->hash;
378 break;
379 }
380 l = &f->hash;
381 }
382 unlock(&palloc.hashlock);
383 putimage(p->image);
384 p->image = 0;
385 p->daddr = 0;
386 }
387
388 void
cachepage(Page * p,Image * i)389 cachepage(Page *p, Image *i)
390 {
391 Page **l;
392
393 /* If this ever happens it should be fixed by calling
394 * uncachepage instead of panic. I think there is a race
395 * with pio in which this can happen. Calling uncachepage is
396 * correct - I just wanted to see if we got here.
397 */
398 if(p->image)
399 panic("cachepage");
400
401 incref(i);
402 lock(&palloc.hashlock);
403 p->image = i;
404 l = &pghash(p->daddr);
405 p->hash = *l;
406 *l = p;
407 unlock(&palloc.hashlock);
408 }
409
410 void
cachedel(Image * i,ulong daddr)411 cachedel(Image *i, ulong daddr)
412 {
413 Page *f, **l;
414
415 lock(&palloc.hashlock);
416 l = &pghash(daddr);
417 for(f = *l; f; f = f->hash) {
418 if(f->image == i && f->daddr == daddr) {
419 lock(f);
420 if(f->image == i && f->daddr == daddr){
421 *l = f->hash;
422 putimage(f->image);
423 f->image = 0;
424 f->daddr = 0;
425 }
426 unlock(f);
427 break;
428 }
429 l = &f->hash;
430 }
431 unlock(&palloc.hashlock);
432 }
433
434 Page *
lookpage(Image * i,ulong daddr)435 lookpage(Image *i, ulong daddr)
436 {
437 Page *f;
438
439 lock(&palloc.hashlock);
440 for(f = pghash(daddr); f; f = f->hash) {
441 if(f->image == i && f->daddr == daddr) {
442 unlock(&palloc.hashlock);
443
444 lock(&palloc);
445 lock(f);
446 if(f->image != i || f->daddr != daddr) {
447 unlock(f);
448 unlock(&palloc);
449 return 0;
450 }
451 if(++f->ref == 1)
452 pageunchain(f);
453 unlock(&palloc);
454 unlock(f);
455
456 return f;
457 }
458 }
459 unlock(&palloc.hashlock);
460
461 return 0;
462 }
463
464 Pte*
ptecpy(Pte * old)465 ptecpy(Pte *old)
466 {
467 Pte *new;
468 Page **src, **dst;
469
470 new = ptealloc();
471 dst = &new->pages[old->first-old->pages];
472 new->first = dst;
473 for(src = old->first; src <= old->last; src++, dst++)
474 if(*src) {
475 if(onswap(*src))
476 dupswap(*src);
477 else {
478 lock(*src);
479 (*src)->ref++;
480 unlock(*src);
481 }
482 new->last = dst;
483 *dst = *src;
484 }
485
486 return new;
487 }
488
489 Pte*
ptealloc(void)490 ptealloc(void)
491 {
492 Pte *new;
493
494 new = smalloc(sizeof(Pte));
495 new->first = &new->pages[PTEPERTAB];
496 new->last = new->pages;
497 return new;
498 }
499
500 void
freepte(Segment * s,Pte * p)501 freepte(Segment *s, Pte *p)
502 {
503 int ref;
504 void (*fn)(Page*);
505 Page *pt, **pg, **ptop;
506
507 switch(s->type&SG_TYPE) {
508 case SG_PHYSICAL:
509 fn = s->pseg->pgfree;
510 ptop = &p->pages[PTEPERTAB];
511 if(fn) {
512 for(pg = p->pages; pg < ptop; pg++) {
513 if(*pg == 0)
514 continue;
515 (*fn)(*pg);
516 *pg = 0;
517 }
518 break;
519 }
520 for(pg = p->pages; pg < ptop; pg++) {
521 pt = *pg;
522 if(pt == 0)
523 continue;
524 lock(pt);
525 ref = --pt->ref;
526 unlock(pt);
527 if(ref == 0)
528 free(pt);
529 }
530 break;
531 default:
532 for(pg = p->first; pg <= p->last; pg++)
533 if(*pg) {
534 putpage(*pg);
535 *pg = 0;
536 }
537 }
538 free(p);
539 }
540
541 ulong
pagenumber(Page * p)542 pagenumber(Page *p)
543 {
544 return p-palloc.pages;
545 }
546
547 void
checkpagerefs(void)548 checkpagerefs(void)
549 {
550 int s;
551 ulong i, np, nwrong;
552 ulong *ref;
553
554 np = palloc.user;
555 ref = malloc(np*sizeof ref[0]);
556 if(ref == nil){
557 print("checkpagerefs: out of memory\n");
558 return;
559 }
560
561 /*
562 * This may not be exact if there are other processes
563 * holding refs to pages on their stacks. The hope is
564 * that if you run it on a quiescent system it will still
565 * be useful.
566 */
567 s = splhi();
568 lock(&palloc);
569 countpagerefs(ref, 0);
570 portcountpagerefs(ref, 0);
571 nwrong = 0;
572 for(i=0; i<np; i++){
573 if(palloc.pages[i].ref != ref[i]){
574 iprint("page %#.8lux ref %d actual %lud\n",
575 palloc.pages[i].pa, palloc.pages[i].ref, ref[i]);
576 ref[i] = 1;
577 nwrong++;
578 }else
579 ref[i] = 0;
580 }
581 countpagerefs(ref, 1);
582 portcountpagerefs(ref, 1);
583 iprint("%lud mistakes found\n", nwrong);
584 unlock(&palloc);
585 splx(s);
586 }
587
588 void
portcountpagerefs(ulong * ref,int print)589 portcountpagerefs(ulong *ref, int print)
590 {
591 ulong i, j, k, ns, n;
592 Page **pg, *entry;
593 Proc *p;
594 Pte *pte;
595 Segment *s;
596
597 /*
598 * Pages in segments. s->mark avoids double-counting.
599 */
600 n = 0;
601 ns = 0;
602 for(i=0; i<conf.nproc; i++){
603 p = proctab(i);
604 for(j=0; j<NSEG; j++){
605 s = p->seg[j];
606 if(s)
607 s->mark = 0;
608 }
609 }
610 for(i=0; i<conf.nproc; i++){
611 p = proctab(i);
612 for(j=0; j<NSEG; j++){
613 s = p->seg[j];
614 if(s == nil || s->mark++)
615 continue;
616 ns++;
617 for(k=0; k<s->mapsize; k++){
618 pte = s->map[k];
619 if(pte == nil)
620 continue;
621 for(pg = pte->first; pg <= pte->last; pg++){
622 entry = *pg;
623 if(pagedout(entry))
624 continue;
625 if(print){
626 if(ref[pagenumber(entry)])
627 iprint("page %#.8lux in segment %#p\n", entry->pa, s);
628 continue;
629 }
630 if(ref[pagenumber(entry)]++ == 0)
631 n++;
632 }
633 }
634 }
635 }
636 if(!print){
637 iprint("%lud pages in %lud segments\n", n, ns);
638 for(i=0; i<conf.nproc; i++){
639 p = proctab(i);
640 for(j=0; j<NSEG; j++){
641 s = p->seg[j];
642 if(s == nil)
643 continue;
644 if(s->ref != s->mark){
645 iprint("segment %#p (used by proc %lud pid %lud) has bad ref count %lud actual %lud\n",
646 s, i, p->pid, s->ref, s->mark);
647 }
648 }
649 }
650 }
651 }
652
653