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