xref: /minix/minix/servers/vm/alloc.c (revision 7f5f010b) 
1 /* This file is concerned with allocating and freeing arbitrary-size blocks of
2  * physical memory.
3  */
4 
5 #define _SYSTEM 1
6 
7 #include <minix/com.h>
8 #include <minix/callnr.h>
9 #include <minix/type.h>
10 #include <minix/config.h>
11 #include <minix/const.h>
12 #include <minix/sysutil.h>
13 #include <minix/syslib.h>
14 #include <minix/debug.h>
15 #include <minix/bitmap.h>
16 
17 #include <sys/mman.h>
18 
19 #include <limits.h>
20 #include <string.h>
21 #include <errno.h>
22 #include <assert.h>
23 #include <memory.h>
24 
25 #include "vm.h"
26 #include "proto.h"
27 #include "util.h"
28 #include "glo.h"
29 #include "sanitycheck.h"
30 #include "memlist.h"
31 
32 /* Number of physical pages in a 32-bit address space */
33 #define NUMBER_PHYSICAL_PAGES (int)(0x100000000ULL/VM_PAGE_SIZE)
34 #define PAGE_BITMAP_CHUNKS BITMAP_CHUNKS(NUMBER_PHYSICAL_PAGES)
35 static bitchunk_t free_pages_bitmap[PAGE_BITMAP_CHUNKS];
36 #define PAGE_CACHE_MAX 10000
37 static int free_page_cache[PAGE_CACHE_MAX];
38 static int free_page_cache_size = 0;
39 
40 /* Used for sanity check. */
41 static phys_bytes mem_low, mem_high;
42 
43 static void free_pages(phys_bytes addr, int pages);
44 static phys_bytes alloc_pages(int pages, int flags);
45 
46 #if SANITYCHECKS
47 struct {
48 	int used;
49 	const char *file;
50 	int line;
51 } pagemap[NUMBER_PHYSICAL_PAGES];
52 #endif
53 
54 #define page_isfree(i) GET_BIT(free_pages_bitmap, i)
55 
56 #define RESERVEDMAGIC		0x6e4c74d5
57 #define MAXRESERVEDPAGES	300
58 #define MAXRESERVEDQUEUES	 15
59 
60 static struct reserved_pages {
61 	struct reserved_pages *next;	/* next in use */
62 	int max_available;	/* queue depth use, 0 if not in use at all */
63 	int npages;		/* number of consecutive pages */
64 	int mappedin;		/* must reserved pages also be mapped? */
65 	int n_available;	/* number of queue entries */
66 	int allocflags;		/* allocflags for alloc_mem */
67 	struct reserved_pageslot {
68 		phys_bytes	phys;
69 		void		*vir;
70 	} slots[MAXRESERVEDPAGES];
71 	u32_t magic;
72 } reservedqueues[MAXRESERVEDQUEUES], *first_reserved_inuse = NULL;
73 
74 int missing_spares = 0;
75 
76 static void sanitycheck_queues(void)
77 {
78 	struct reserved_pages *mrq;
79 	int m = 0;
80 
81 	for(mrq = first_reserved_inuse; mrq; mrq = mrq->next) {
82 		assert(mrq->max_available > 0);
83 		assert(mrq->max_available >= mrq->n_available);
84 		m += mrq->max_available - mrq->n_available;
85 	}
86 
87 	assert(m == missing_spares);
88 }
89 
90 static void sanitycheck_rq(struct reserved_pages *rq)
91 {
92 	assert(rq->magic == RESERVEDMAGIC);
93 	assert(rq->n_available >= 0);
94 	assert(rq->n_available <= MAXRESERVEDPAGES);
95 	assert(rq->n_available <= rq->max_available);
96 
97 	sanitycheck_queues();
98 }
99 
100 void *reservedqueue_new(int max_available, int npages, int mapped, int allocflags)
101 {
102 	int r;
103 	struct reserved_pages *rq;
104 
105 	assert(max_available > 0);
106 	assert(max_available < MAXRESERVEDPAGES);
107 	assert(npages > 0);
108 	assert(npages < 10);
109 
110 	for(r = 0; r < MAXRESERVEDQUEUES; r++)
111 		if(!reservedqueues[r].max_available)
112 			break;
113 
114 	if(r >= MAXRESERVEDQUEUES) {
115 		printf("VM: %d reserved queues in use\n", MAXRESERVEDQUEUES);
116 		return NULL;
117 	}
118 
119 	rq = &reservedqueues[r];
120 
121 	memset(rq, 0, sizeof(*rq));
122 	rq->next = first_reserved_inuse;
123 	first_reserved_inuse = rq;
124 
125 	rq->max_available = max_available;
126 	rq->npages = npages;
127 	rq->mappedin = mapped;
128 	rq->allocflags = allocflags;
129 	rq->magic = RESERVEDMAGIC;
130 
131 	missing_spares += max_available;
132 
133 	return rq;
134 }
135 
136 static void
137 reservedqueue_fillslot(struct reserved_pages *rq,
138 	struct reserved_pageslot *rps, phys_bytes ph, void *vir)
139 {
140 	rps->phys = ph;
141 	rps->vir = vir;
142 	assert(missing_spares > 0);
143 	if(rq->mappedin) assert(vir);
144 	missing_spares--;
145 	rq->n_available++;
146 }
147 
148 static int
149 reservedqueue_addslot(struct reserved_pages *rq)
150 {
151 	phys_bytes cl, cl_addr;
152 	void *vir;
153 	struct reserved_pageslot *rps;
154 
155 	sanitycheck_rq(rq);
156 
157 	if((cl = alloc_mem(rq->npages, rq->allocflags)) == NO_MEM)
158 		return ENOMEM;
159 
160 	cl_addr = CLICK2ABS(cl);
161 
162 	vir = NULL;
163 
164 	if(rq->mappedin) {
165 		if(!(vir = vm_mappages(cl_addr, rq->npages))) {
166 			free_mem(cl, rq->npages);
167 			printf("reservedqueue_addslot: vm_mappages failed\n");
168 			return ENOMEM;
169 		}
170 	}
171 
172 	rps = &rq->slots[rq->n_available];
173 
174 	reservedqueue_fillslot(rq, rps, cl_addr, vir);
175 
176 	return OK;
177 }
178 
179 void reservedqueue_add(void *rq_v, void *vir, phys_bytes ph)
180 {
181 	struct reserved_pages *rq = rq_v;
182 	struct reserved_pageslot *rps;
183 
184 	sanitycheck_rq(rq);
185 
186 	rps = &rq->slots[rq->n_available];
187 
188 	reservedqueue_fillslot(rq, rps, ph, vir);
189 }
190 
191 static int reservedqueue_fill(void *rq_v)
192 {
193 	struct reserved_pages *rq = rq_v;
194 	int r;
195 
196 	sanitycheck_rq(rq);
197 
198 	while(rq->n_available < rq->max_available)
199 		if((r=reservedqueue_addslot(rq)) != OK)
200 			return r;
201 
202 	return OK;
203 }
204 
205 int
206 reservedqueue_alloc(void *rq_v, phys_bytes *ph, void **vir)
207 {
208 	struct reserved_pages *rq = rq_v;
209 	struct reserved_pageslot *rps;
210 
211 	sanitycheck_rq(rq);
212 
213 	if(rq->n_available < 1) return ENOMEM;
214 
215 	rq->n_available--;
216 	missing_spares++;
217 	rps = &rq->slots[rq->n_available];
218 
219 	*ph = rps->phys;
220 	*vir = rps->vir;
221 
222 	sanitycheck_rq(rq);
223 
224 	return OK;
225 }
226 
227 void alloc_cycle(void)
228 {
229 	struct reserved_pages *rq;
230 	sanitycheck_queues();
231 	for(rq = first_reserved_inuse; rq && missing_spares > 0; rq = rq->next) {
232 		sanitycheck_rq(rq);
233 		reservedqueue_fill(rq);
234 		sanitycheck_rq(rq);
235 	}
236 	sanitycheck_queues();
237 }
238 
239 /*===========================================================================*
240  *				alloc_mem				     *
241  *===========================================================================*/
242 phys_clicks alloc_mem(phys_clicks clicks, u32_t memflags)
243 {
244 /* Allocate a block of memory from the free list using first fit. The block
245  * consists of a sequence of contiguous bytes, whose length in clicks is
246  * given by 'clicks'.  A pointer to the block is returned.  The block is
247  * always on a click boundary.  This procedure is called when memory is
248  * needed for FORK or EXEC.
249  */
250   phys_clicks mem = NO_MEM, align_clicks = 0;
251 
252   if(memflags & PAF_ALIGN64K) {
253   	align_clicks = (64 * 1024) / CLICK_SIZE;
254 	clicks += align_clicks;
255   } else if(memflags & PAF_ALIGN16K) {
256 	align_clicks = (16 * 1024) / CLICK_SIZE;
257 	clicks += align_clicks;
258   }
259 
260   do {
261 	mem = alloc_pages(clicks, memflags);
262   } while(mem == NO_MEM && cache_freepages(clicks) > 0);
263 
264   if(mem == NO_MEM)
265   	return mem;
266 
267   if(align_clicks) {
268   	phys_clicks o;
269   	o = mem % align_clicks;
270   	if(o > 0) {
271   		phys_clicks e;
272   		e = align_clicks - o;
273 	  	free_mem(mem, e);
274 	  	mem += e;
275 	}
276   }
277 
278   return mem;
279 }
280 
281 void mem_add_total_pages(int pages)
282 {
283 	total_pages += pages;
284 }
285 
286 /*===========================================================================*
287  *				free_mem				     *
288  *===========================================================================*/
289 void free_mem(phys_clicks base, phys_clicks clicks)
290 {
291 /* Return a block of free memory to the hole list.  The parameters tell where
292  * the block starts in physical memory and how big it is.  The block is added
293  * to the hole list.  If it is contiguous with an existing hole on either end,
294  * it is merged with the hole or holes.
295  */
296   if (clicks == 0) return;
297 
298   assert(CLICK_SIZE == VM_PAGE_SIZE);
299   free_pages(base, clicks);
300   return;
301 }
302 
303 /*===========================================================================*
304  *				mem_init				     *
305  *===========================================================================*/
306 void mem_init(struct memory *chunks)
307 {
308 /* Initialize hole lists.  There are two lists: 'hole_head' points to a linked
309  * list of all the holes (unused memory) in the system; 'free_slots' points to
310  * a linked list of table entries that are not in use.  Initially, the former
311  * list has one entry for each chunk of physical memory, and the second
312  * list links together the remaining table slots.  As memory becomes more
313  * fragmented in the course of time (i.e., the initial big holes break up into
314  * smaller holes), new table slots are needed to represent them.  These slots
315  * are taken from the list headed by 'free_slots'.
316  */
317   int i, first = 0;
318 
319   total_pages = 0;
320 
321   memset(free_pages_bitmap, 0, sizeof(free_pages_bitmap));
322 
323   /* Use the chunks of physical memory to allocate holes. */
324   for (i=NR_MEMS-1; i>=0; i--) {
325   	if (chunks[i].size > 0) {
326 		phys_bytes from = CLICK2ABS(chunks[i].base),
327 			to = CLICK2ABS(chunks[i].base+chunks[i].size)-1;
328 		if(first || from < mem_low) mem_low = from;
329 		if(first || to > mem_high) mem_high = to;
330 		free_mem(chunks[i].base, chunks[i].size);
331 		total_pages += chunks[i].size;
332 		first = 0;
333 	}
334   }
335 }
336 
337 #if SANITYCHECKS
338 void mem_sanitycheck(const char *file, int line)
339 {
340 	int i;
341 	for(i = 0; i < NUMBER_PHYSICAL_PAGES; i++) {
342 		if(!page_isfree(i)) continue;
343 		MYASSERT(usedpages_add(i * VM_PAGE_SIZE, VM_PAGE_SIZE) == OK);
344 	}
345 }
346 #endif
347 
348 void memstats(int *nodes, int *pages, int *largest)
349 {
350 	int i;
351 	*nodes = 0;
352 	*pages = 0;
353 	*largest = 0;
354 
355 	for(i = 0; i < NUMBER_PHYSICAL_PAGES; i++) {
356 		int size = 0;
357 		while(i < NUMBER_PHYSICAL_PAGES && page_isfree(i)) {
358 			size++;
359 			i++;
360 		}
361 		if(size == 0) continue;
362 		(*nodes)++;
363 		(*pages)+= size;
364 		if(size > *largest)
365 			*largest = size;
366 	}
367 }
368 
369 static int findbit(int low, int startscan, int pages, int memflags, int *len)
370 {
371 	int run_length = 0, i;
372 	int freerange_start = startscan;
373 
374 	for(i = startscan; i >= low; i--) {
375 		if(!page_isfree(i)) {
376 			int pi;
377 			int chunk = i/BITCHUNK_BITS, moved = 0;
378 			run_length = 0;
379 			pi = i;
380 			while(chunk > 0 &&
381 			   !MAP_CHUNK(free_pages_bitmap, chunk*BITCHUNK_BITS)) {
382 				chunk--;
383 				moved = 1;
384 			}
385 			if(moved) { i = chunk * BITCHUNK_BITS + BITCHUNK_BITS; }
386 			continue;
387 		}
388 		if(!run_length) { freerange_start = i; run_length = 1; }
389 		else { freerange_start--; run_length++; }
390 		assert(run_length <= pages);
391 		if(run_length == pages) {
392 			/* good block found! */
393 			*len = run_length;
394 			return freerange_start;
395 		}
396 	}
397 
398 	return NO_MEM;
399 }
400 
401 /*===========================================================================*
402  *				alloc_pages				     *
403  *===========================================================================*/
404 static phys_bytes alloc_pages(int pages, int memflags)
405 {
406 	phys_bytes boundary16 = 16 * 1024 * 1024 / VM_PAGE_SIZE;
407 	phys_bytes boundary1  =  1 * 1024 * 1024 / VM_PAGE_SIZE;
408 	phys_bytes mem = NO_MEM, i;	/* page number */
409 	int maxpage = NUMBER_PHYSICAL_PAGES - 1;
410 	static int lastscan = -1;
411 	int startscan, run_length;
412 
413 	if(memflags & PAF_LOWER16MB)
414 		maxpage = boundary16 - 1;
415 	else if(memflags & PAF_LOWER1MB)
416 		maxpage = boundary1 - 1;
417 	else {
418 		/* no position restrictions: check page cache */
419 		if(pages == 1) {
420 			while(free_page_cache_size > 0) {
421 				i = free_page_cache[free_page_cache_size-1];
422 				if(page_isfree(i)) {
423 					free_page_cache_size--;
424 					mem = i;
425 					assert(mem != NO_MEM);
426 					run_length = 1;
427 					break;
428 				}
429 				free_page_cache_size--;
430 			}
431 		}
432 	}
433 
434 	if(lastscan < maxpage && lastscan >= 0)
435 		startscan = lastscan;
436 	else	startscan = maxpage;
437 
438 	if(mem == NO_MEM)
439 		mem = findbit(0, startscan, pages, memflags, &run_length);
440 	if(mem == NO_MEM)
441 		mem = findbit(0, maxpage, pages, memflags, &run_length);
442 	if(mem == NO_MEM)
443 		return NO_MEM;
444 
445 	/* remember for next time */
446 	lastscan = mem;
447 
448 	for(i = mem; i < mem + pages; i++) {
449 		UNSET_BIT(free_pages_bitmap, i);
450 	}
451 
452 	if(memflags & PAF_CLEAR) {
453 		int s;
454 		if ((s= sys_memset(NONE, 0, CLICK_SIZE*mem,
455 			VM_PAGE_SIZE*pages)) != OK)
456 			panic("alloc_mem: sys_memset failed: %d", s);
457 	}
458 
459 	return mem;
460 }
461 
462 /*===========================================================================*
463  *				free_pages				     *
464  *===========================================================================*/
465 static void free_pages(phys_bytes pageno, int npages)
466 {
467 	int i, lim = pageno + npages - 1;
468 
469 #if JUNKFREE
470        if(sys_memset(NONE, 0xa5a5a5a5, VM_PAGE_SIZE * pageno,
471                VM_PAGE_SIZE * npages) != OK)
472                        panic("free_pages: sys_memset failed");
473 #endif
474 
475 	for(i = pageno; i <= lim; i++) {
476 		SET_BIT(free_pages_bitmap, i);
477 		if(free_page_cache_size < PAGE_CACHE_MAX) {
478 			free_page_cache[free_page_cache_size++] = i;
479 		}
480 	}
481 }
482 
483 /*===========================================================================*
484  *				printmemstats				     *
485  *===========================================================================*/
486 void printmemstats(void)
487 {
488 	int nodes, pages, largest;
489         memstats(&nodes, &pages, &largest);
490         printf("%d blocks, %d pages (%lukB) free, largest %d pages (%lukB)\n",
491                 nodes, pages, (unsigned long) pages * (VM_PAGE_SIZE/1024),
492 		largest, (unsigned long) largest * (VM_PAGE_SIZE/1024));
493 }
494 
495 
496 #if SANITYCHECKS
497 
498 /*===========================================================================*
499  *				usedpages_reset				     *
500  *===========================================================================*/
501 void usedpages_reset(void)
502 {
503 	memset(pagemap, 0, sizeof(pagemap));
504 }
505 
506 /*===========================================================================*
507  *				usedpages_add				     *
508  *===========================================================================*/
509 int usedpages_add_f(phys_bytes addr, phys_bytes len, const char *file, int line)
510 {
511 	u32_t pagestart, pages;
512 
513 	if(!incheck)
514 		return OK;
515 
516 	assert(!(addr % VM_PAGE_SIZE));
517 	assert(!(len % VM_PAGE_SIZE));
518 	assert(len > 0);
519 
520 	pagestart = addr / VM_PAGE_SIZE;
521 	pages = len / VM_PAGE_SIZE;
522 
523 	while(pages > 0) {
524 		phys_bytes thisaddr;
525 		assert(pagestart > 0);
526 		assert(pagestart < NUMBER_PHYSICAL_PAGES);
527 		thisaddr = pagestart * VM_PAGE_SIZE;
528 		assert(pagestart < NUMBER_PHYSICAL_PAGES);
529 		if(pagemap[pagestart].used) {
530 			static int warnings = 0;
531 			if(warnings++ < 100)
532 				printf("%s:%d: usedpages_add: addr 0x%lx reused, first %s:%d\n",
533 					file, line, thisaddr, pagemap[pagestart].file, pagemap[pagestart].line);
534 			util_stacktrace();
535 			return EFAULT;
536 		}
537 		pagemap[pagestart].used = 1;
538 		pagemap[pagestart].file = file;
539 		pagemap[pagestart].line = line;
540 		pages--;
541 		pagestart++;
542 	}
543 
544 	return OK;
545 }
546 
547 #endif
548 
549