Index: kernel/arch/abs32le/include/arch/mm/frame.h =================================================================== --- kernel/arch/abs32le/include/arch/mm/frame.h (revision 6e75f2dcda90e74dfeaa38430a08f747bf4e05fe) +++ kernel/arch/abs32le/include/arch/mm/frame.h (revision d7b7f5e312adb3acb6e7c2044551454dfd1e4019) @@ -39,4 +39,6 @@ #define FRAME_SIZE (1 << FRAME_WIDTH) +#define FRAME_LOWPRIO 0 + #include Index: kernel/arch/amd64/include/arch/mm/frame.h =================================================================== --- kernel/arch/amd64/include/arch/mm/frame.h (revision 6e75f2dcda90e74dfeaa38430a08f747bf4e05fe) +++ kernel/arch/amd64/include/arch/mm/frame.h (revision d7b7f5e312adb3acb6e7c2044551454dfd1e4019) @@ -39,4 +39,6 @@ #define FRAME_SIZE (1 << FRAME_WIDTH) +#define FRAME_LOWPRIO 0x1000 + #ifndef __ASM__ Index: kernel/arch/arm32/include/arch/mm/frame.h =================================================================== --- kernel/arch/arm32/include/arch/mm/frame.h (revision 6e75f2dcda90e74dfeaa38430a08f747bf4e05fe) +++ kernel/arch/arm32/include/arch/mm/frame.h (revision d7b7f5e312adb3acb6e7c2044551454dfd1e4019) @@ -39,4 +39,6 @@ #define FRAME_WIDTH 12 /* 4KB frames */ #define FRAME_SIZE (1 << FRAME_WIDTH) + +#define FRAME_LOWPRIO 0 #ifndef __ASM__ Index: kernel/arch/ia32/include/arch/mm/frame.h =================================================================== --- kernel/arch/ia32/include/arch/mm/frame.h (revision 6e75f2dcda90e74dfeaa38430a08f747bf4e05fe) +++ kernel/arch/ia32/include/arch/mm/frame.h (revision d7b7f5e312adb3acb6e7c2044551454dfd1e4019) @@ -39,4 +39,6 @@ #define FRAME_SIZE (1 << FRAME_WIDTH) +#define FRAME_LOWPRIO 0x1000 + #ifndef __ASM__ Index: kernel/arch/ia64/include/arch/mm/frame.h =================================================================== --- kernel/arch/ia64/include/arch/mm/frame.h (revision 6e75f2dcda90e74dfeaa38430a08f747bf4e05fe) +++ kernel/arch/ia64/include/arch/mm/frame.h (revision d7b7f5e312adb3acb6e7c2044551454dfd1e4019) @@ -39,4 +39,6 @@ #define FRAME_SIZE (1 << FRAME_WIDTH) +#define FRAME_LOWPRIO 0 + #ifndef __ASM__ Index: kernel/arch/mips32/include/arch/mm/frame.h =================================================================== --- kernel/arch/mips32/include/arch/mm/frame.h (revision 6e75f2dcda90e74dfeaa38430a08f747bf4e05fe) +++ kernel/arch/mips32/include/arch/mm/frame.h (revision d7b7f5e312adb3acb6e7c2044551454dfd1e4019) @@ -39,4 +39,6 @@ #define FRAME_SIZE (1 << FRAME_WIDTH) +#define FRAME_LOWPRIO 0 + #ifndef __ASM__ Index: kernel/arch/mips64/include/arch/mm/frame.h =================================================================== --- kernel/arch/mips64/include/arch/mm/frame.h (revision 6e75f2dcda90e74dfeaa38430a08f747bf4e05fe) +++ kernel/arch/mips64/include/arch/mm/frame.h (revision d7b7f5e312adb3acb6e7c2044551454dfd1e4019) @@ -39,4 +39,6 @@ #define FRAME_SIZE (1 << FRAME_WIDTH) +#define FRAME_LOWPRIO 0 + #ifndef __ASM__ Index: kernel/arch/ppc32/include/arch/mm/frame.h =================================================================== --- kernel/arch/ppc32/include/arch/mm/frame.h (revision 6e75f2dcda90e74dfeaa38430a08f747bf4e05fe) +++ kernel/arch/ppc32/include/arch/mm/frame.h (revision d7b7f5e312adb3acb6e7c2044551454dfd1e4019) @@ -39,4 +39,6 @@ #define FRAME_SIZE (1 << FRAME_WIDTH) +#define FRAME_LOWPRIO 0 + #ifndef __ASM__ Index: kernel/arch/sparc64/include/arch/mm/sun4u/frame.h =================================================================== --- kernel/arch/sparc64/include/arch/mm/sun4u/frame.h (revision 6e75f2dcda90e74dfeaa38430a08f747bf4e05fe) +++ kernel/arch/sparc64/include/arch/mm/sun4u/frame.h (revision d7b7f5e312adb3acb6e7c2044551454dfd1e4019) @@ -27,5 +27,5 @@ */ -/** @addtogroup sparc64mm +/** @addtogroup sparc64mm * @{ */ @@ -41,6 +41,6 @@ * Therefore, the kernel uses 8K only internally on the TLB and TSB levels. */ -#define MMU_FRAME_WIDTH 13 /* 8K */ -#define MMU_FRAME_SIZE (1 << MMU_FRAME_WIDTH) +#define MMU_FRAME_WIDTH 13 /* 8K */ +#define MMU_FRAME_SIZE (1 << MMU_FRAME_WIDTH) /* @@ -49,6 +49,8 @@ * each 16K page with a pair of adjacent 8K pages. */ -#define FRAME_WIDTH 14 /* 16K */ -#define FRAME_SIZE (1 << FRAME_WIDTH) +#define FRAME_WIDTH 14 /* 16K */ +#define FRAME_SIZE (1 << FRAME_WIDTH) + +#define FRAME_LOWPRIO 0 #ifndef __ASM__ Index: kernel/arch/sparc64/include/arch/mm/sun4v/frame.h =================================================================== --- kernel/arch/sparc64/include/arch/mm/sun4v/frame.h (revision 6e75f2dcda90e74dfeaa38430a08f747bf4e05fe) +++ kernel/arch/sparc64/include/arch/mm/sun4v/frame.h (revision d7b7f5e312adb3acb6e7c2044551454dfd1e4019) @@ -27,5 +27,5 @@ */ -/** @addtogroup sparc64mm +/** @addtogroup sparc64mm * @{ */ @@ -36,9 +36,11 @@ #define KERN_sparc64_sun4v_FRAME_H_ -#define MMU_FRAME_WIDTH 13 /* 8K */ -#define MMU_FRAME_SIZE (1 << MMU_FRAME_WIDTH) +#define MMU_FRAME_WIDTH 13 /* 8K */ +#define MMU_FRAME_SIZE (1 << MMU_FRAME_WIDTH) -#define FRAME_WIDTH 13 -#define FRAME_SIZE (1 << FRAME_WIDTH) +#define FRAME_WIDTH 13 +#define FRAME_SIZE (1 << FRAME_WIDTH) + +#define FRAME_LOWPRIO 0 #endif Index: kernel/generic/include/adt/bitmap.h =================================================================== --- kernel/generic/include/adt/bitmap.h (revision 6e75f2dcda90e74dfeaa38430a08f747bf4e05fe) +++ kernel/generic/include/adt/bitmap.h (revision d7b7f5e312adb3acb6e7c2044551454dfd1e4019) @@ -81,5 +81,6 @@ extern void bitmap_clear_range(bitmap_t *, size_t, size_t); -extern int bitmap_allocate_range(bitmap_t *, size_t, size_t, size_t, size_t *); +extern int bitmap_allocate_range(bitmap_t *, size_t, size_t, size_t, size_t, + size_t *); extern void bitmap_copy(bitmap_t *, bitmap_t *, size_t); Index: kernel/generic/include/mm/frame.h =================================================================== --- kernel/generic/include/mm/frame.h (revision 6e75f2dcda90e74dfeaa38430a08f747bf4e05fe) +++ kernel/generic/include/mm/frame.h (revision d7b7f5e312adb3acb6e7c2044551454dfd1e4019) @@ -131,7 +131,7 @@ extern void frame_init(void); extern bool frame_adjust_zone_bounds(bool, uintptr_t *, size_t *); -extern uintptr_t frame_alloc_generic(size_t, frame_flags_t, uintptr_t, size_t *); +extern uintptr_t frame_alloc_generic(size_t, frame_flags_t, uintptr_t, + size_t *); extern uintptr_t frame_alloc(size_t, frame_flags_t, uintptr_t); -extern uintptr_t frame_alloc_noreserve(size_t, frame_flags_t, uintptr_t); extern void frame_free_generic(uintptr_t, size_t, frame_flags_t); extern void frame_free(uintptr_t, size_t); Index: kernel/generic/src/adt/bitmap.c =================================================================== --- kernel/generic/src/adt/bitmap.c (revision 6e75f2dcda90e74dfeaa38430a08f747bf4e05fe) +++ kernel/generic/src/adt/bitmap.c (revision d7b7f5e312adb3acb6e7c2044551454dfd1e4019) @@ -258,4 +258,5 @@ * @param count Number of continuous zero bits to find. * @param base Address of the first bit in the bitmap. + * @param prefered Prefered address to start searching from. * @param constraint Constraint for the address of the first zero bit. * @param index Place to store the index of the first zero @@ -269,5 +270,5 @@ */ int bitmap_allocate_range(bitmap_t *bitmap, size_t count, size_t base, - size_t constraint, size_t *index) + size_t prefered, size_t constraint, size_t *index) { if (count == 0) @@ -275,7 +276,19 @@ size_t size = bitmap_size(bitmap->elements); + size_t next_fit = bitmap->next_fit; + + /* + * Adjust the next-fit value according to the address + * the caller prefers to start the search at. + */ + if ((prefered > base) && (prefered < base + bitmap->elements)) { + size_t prefered_fit = (prefered - base) / BITMAP_ELEMENT; + + if (prefered_fit > next_fit) + next_fit = prefered_fit; + } for (size_t pos = 0; pos < size; pos++) { - size_t byte = (bitmap->next_fit + pos) % size; + size_t byte = (next_fit + pos) % size; /* Skip if the current byte has all bits set */ Index: kernel/generic/src/ddi/ddi.c =================================================================== --- kernel/generic/src/ddi/ddi.c (revision 6e75f2dcda90e74dfeaa38430a08f747bf4e05fe) +++ kernel/generic/src/ddi/ddi.c (revision d7b7f5e312adb3acb6e7c2044551454dfd1e4019) @@ -329,5 +329,5 @@ size_t frames = SIZE2FRAMES(size); - *phys = frame_alloc_noreserve(frames, 0, constraint); + *phys = frame_alloc(frames, FRAME_NO_RESERVE, constraint); if (*phys == 0) return ENOMEM; Index: kernel/generic/src/mm/frame.c =================================================================== --- kernel/generic/src/mm/frame.c (revision 6e75f2dcda90e74dfeaa38430a08f747bf4e05fe) +++ kernel/generic/src/mm/frame.c (revision d7b7f5e312adb3acb6e7c2044551454dfd1e4019) @@ -234,7 +234,91 @@ * the bitmap if the last argument is NULL. */ + return ((zone->flags & ZONE_AVAILABLE) && bitmap_allocate_range(&zone->bitmap, count, zone->base, - constraint, NULL)); + FRAME_LOWPRIO, constraint, NULL)); +} + +/** Find a zone that can allocate specified number of frames + * + * This function searches among all zones. Assume interrupts are + * disabled and zones lock is locked. + * + * @param count Number of free frames we are trying to find. + * @param flags Required flags of the zone. + * @param constraint Indication of bits that cannot be set in the + * physical frame number of the first allocated frame. + * @param hint Preferred zone. + * + * @return Zone that can allocate specified number of frames. + * @return -1 if no zone can satisfy the request. + * + */ +NO_TRACE static size_t find_free_zone_all(size_t count, zone_flags_t flags, + pfn_t constraint, size_t hint) +{ + for (size_t pos = 0; pos < zones.count; pos++) { + size_t i = (pos + hint) % zones.count; + + /* Check whether the zone meets the search criteria. */ + if (!ZONE_FLAGS_MATCH(zones.info[i].flags, flags)) + continue; + + /* Check if the zone can satisfy the allocation request. */ + if (zone_can_alloc(&zones.info[i], count, constraint)) + return i; + } + + return (size_t) -1; +} + +/** Check if frame range priority memory + * + * @param pfn Starting frame. + * @param count Number of frames. + * + * @return True if the range contains only priority memory. + * + */ +NO_TRACE static bool is_high_priority(pfn_t base, size_t count) +{ + return (base + count <= FRAME_LOWPRIO); +} + +/** Find a zone that can allocate specified number of frames + * + * This function ignores zones that contain only high-priority + * memory. Assume interrupts are disabled and zones lock is locked. + * + * @param count Number of free frames we are trying to find. + * @param flags Required flags of the zone. + * @param constraint Indication of bits that cannot be set in the + * physical frame number of the first allocated frame. + * @param hint Preferred zone. + * + * @return Zone that can allocate specified number of frames. + * @return -1 if no low-priority zone can satisfy the request. + * + */ +NO_TRACE static size_t find_free_zone_lowprio(size_t count, zone_flags_t flags, + pfn_t constraint, size_t hint) +{ + for (size_t pos = 0; pos < zones.count; pos++) { + size_t i = (pos + hint) % zones.count; + + /* Skip zones containing only high-priority memory. */ + if (is_high_priority(zones.info[i].base, zones.info[i].count)) + continue; + + /* Check whether the zone meets the search criteria. */ + if (!ZONE_FLAGS_MATCH(zones.info[i].flags, flags)) + continue; + + /* Check if the zone can satisfy the allocation request. */ + if (zone_can_alloc(&zones.info[i], count, constraint)) + return i; + } + + return (size_t) -1; } @@ -248,5 +332,8 @@ * @param constraint Indication of bits that cannot be set in the * physical frame number of the first allocated frame. - * @param hind Preferred zone. + * @param hint Preferred zone. + * + * @return Zone that can allocate specified number of frames. + * @return -1 if no zone can satisfy the request. * */ @@ -257,24 +344,15 @@ hint = 0; - size_t i = hint; - do { - /* - * Check whether the zone meets the search criteria. - */ - if (ZONE_FLAGS_MATCH(zones.info[i].flags, flags)) { - /* - * Check if the zone can satisfy the allocation request. - */ - if (zone_can_alloc(&zones.info[i], count, constraint)) - return i; - } - - i++; - if (i >= zones.count) - i = 0; - - } while (i != hint); - - return (size_t) -1; + /* + * Prefer zones with low-priority memory over + * zones with high-priority memory. + */ + + size_t znum = find_free_zone_lowprio(count, flags, constraint, hint); + if (znum != (size_t) -1) + return znum; + + /* Take all zones into account */ + return find_free_zone_all(count, flags, constraint, hint); } @@ -312,5 +390,5 @@ size_t index; int avail = bitmap_allocate_range(&zone->bitmap, count, zone->base, - constraint, &index); + FRAME_LOWPRIO, constraint, &index); ASSERT(avail); @@ -883,11 +961,4 @@ } -uintptr_t frame_alloc_noreserve(size_t count, frame_flags_t flags, - uintptr_t constraint) -{ - return frame_alloc_generic(count, flags | FRAME_NO_RESERVE, constraint, - NULL); -} - /** Free frames of physical memory. * @@ -1137,5 +1208,5 @@ /* * Because printing may require allocation of memory, we may not hold - * the frame allocator locks when printing zone statistics. Therefore, + * the frame allocator locks when printing zone statistics. Therefore, * we simply gather the statistics under the protection of the locks and * print the statistics when the locks have been released. @@ -1146,4 +1217,8 @@ */ + size_t free_lowmem = 0; + size_t free_highmem = 0; + size_t free_highprio = 0; + for (size_t i = 0;; i++) { irq_spinlock_lock(&zones.lock, true); @@ -1154,5 +1229,6 @@ } - uintptr_t base = PFN2ADDR(zones.info[i].base); + pfn_t fbase = zones.info[i].base; + uintptr_t base = PFN2ADDR(fbase); size_t count = zones.info[i].count; zone_flags_t flags = zones.info[i].flags; @@ -1160,7 +1236,36 @@ size_t busy_count = zones.info[i].busy_count; + bool available = ((flags & ZONE_AVAILABLE) != 0); + bool lowmem = ((flags & ZONE_LOWMEM) != 0); + bool highmem = ((flags & ZONE_HIGHMEM) != 0); + bool highprio = is_high_priority(fbase, count); + + if (available) { + if (lowmem) + free_lowmem += free_count; + + if (highmem) + free_highmem += free_count; + + if (highprio) { + free_highprio += free_count; + } else { + /* + * Walk all frames of the zone and examine + * all high priority memory to get accurate + * statistics. + */ + + for (size_t index = 0; index < count; index++) { + if (is_high_priority(fbase + index, 0)) { + if (!bitmap_get(&zones.info[i].bitmap, index)) + free_highprio++; + } else + break; + } + } + } + irq_spinlock_unlock(&zones.lock, true); - - bool available = ((flags & ZONE_AVAILABLE) != 0); printf("%-4zu", i); @@ -1187,4 +1292,24 @@ printf("\n"); } + + printf("\n"); + + uint64_t size; + const char *size_suffix; + + bin_order_suffix(FRAMES2SIZE(free_lowmem), &size, &size_suffix, + false); + printf("Available low memory: %zu frames (%" PRIu64 " %s)\n", + free_lowmem, size, size_suffix); + + bin_order_suffix(FRAMES2SIZE(free_highmem), &size, &size_suffix, + false); + printf("Available high memory: %zu frames (%" PRIu64 " %s)\n", + free_highmem, size, size_suffix); + + bin_order_suffix(FRAMES2SIZE(free_highprio), &size, &size_suffix, + false); + printf("Available high priority: %zu frames (%" PRIu64 " %s)\n", + free_highprio, size, size_suffix); } @@ -1212,5 +1337,10 @@ } - uintptr_t base = PFN2ADDR(zones.info[znum].base); + size_t free_lowmem = 0; + size_t free_highmem = 0; + size_t free_highprio = 0; + + pfn_t fbase = zones.info[znum].base; + uintptr_t base = PFN2ADDR(fbase); zone_flags_t flags = zones.info[znum].flags; size_t count = zones.info[znum].count; @@ -1218,17 +1348,47 @@ size_t busy_count = zones.info[znum].busy_count; + bool available = ((flags & ZONE_AVAILABLE) != 0); + bool lowmem = ((flags & ZONE_LOWMEM) != 0); + bool highmem = ((flags & ZONE_HIGHMEM) != 0); + bool highprio = is_high_priority(fbase, count); + + if (available) { + if (lowmem) + free_lowmem = free_count; + + if (highmem) + free_highmem = free_count; + + if (highprio) { + free_highprio = free_count; + } else { + /* + * Walk all frames of the zone and examine + * all high priority memory to get accurate + * statistics. + */ + + for (size_t index = 0; index < count; index++) { + if (is_high_priority(fbase + index, 0)) { + if (!bitmap_get(&zones.info[znum].bitmap, index)) + free_highprio++; + } else + break; + } + } + } + irq_spinlock_unlock(&zones.lock, true); - - bool available = ((flags & ZONE_AVAILABLE) != 0); uint64_t size; const char *size_suffix; + bin_order_suffix(FRAMES2SIZE(count), &size, &size_suffix, false); - printf("Zone number: %zu\n", znum); - printf("Zone base address: %p\n", (void *) base); - printf("Zone size: %zu frames (%" PRIu64 " %s)\n", count, + printf("Zone number: %zu\n", znum); + printf("Zone base address: %p\n", (void *) base); + printf("Zone size: %zu frames (%" PRIu64 " %s)\n", count, size, size_suffix); - printf("Zone flags: %c%c%c%c%c\n", + printf("Zone flags: %c%c%c%c%c\n", available ? 'A' : '-', (flags & ZONE_RESERVED) ? 'R' : '-', @@ -1240,10 +1400,26 @@ bin_order_suffix(FRAMES2SIZE(busy_count), &size, &size_suffix, false); - printf("Allocated space: %zu frames (%" PRIu64 " %s)\n", + printf("Allocated space: %zu frames (%" PRIu64 " %s)\n", busy_count, size, size_suffix); + bin_order_suffix(FRAMES2SIZE(free_count), &size, &size_suffix, false); - printf("Available space: %zu frames (%" PRIu64 " %s)\n", + printf("Available space: %zu frames (%" PRIu64 " %s)\n", free_count, size, size_suffix); + + bin_order_suffix(FRAMES2SIZE(free_lowmem), &size, &size_suffix, + false); + printf("Available low memory: %zu frames (%" PRIu64 " %s)\n", + free_lowmem, size, size_suffix); + + bin_order_suffix(FRAMES2SIZE(free_highmem), &size, &size_suffix, + false); + printf("Available high memory: %zu frames (%" PRIu64 " %s)\n", + free_highmem, size, size_suffix); + + bin_order_suffix(FRAMES2SIZE(free_highprio), &size, &size_suffix, + false); + printf("Available high priority: %zu frames (%" PRIu64 " %s)\n", + free_highprio, size, size_suffix); } }