Warning, cross-references for /kernel/mem/pow2.c need to be fixed.
0001
0002
0003
0004
0005
0006
0007
0008
0009
0010
0011
0012
0013
0014
0015
0016
0017
0018 #include "kernel.h"
0019 #include "mem/mem.h"
0020 #include "smp/spinlock.h"
0021
0022
0023
0024
0025 #define POW2_MIN_POW 5
0026 #define POW2_MAX_POW 16
0027
0028
0029
0030
0031
0032
0033 #define POW2_MIN_SIZE (1<<POW2_MIN_POW)
0034 #define POW2_MAX_SIZE (1<<POW2_MAX_POW)
0035
0036
0037 #define POW2_TABLE_LEN ((POW2_MAX_POW - POW2_MIN_POW)+1)
0038
0039
0040 #define POW2_MAX_POW_FRAMES (1 << (POW2_MAX_POW - 12))
0041
0042
0043 #define POW2_MASK_POW ((1<<POW2_MIN_POW)-1)
0044
0045 struct _POW2_HEADER
0046 {
0047 struct _POW2_HEADER *next;
0048 uint32 count;
0049 uint8 *ptrs[0];
0050 } PACKED;
0051 typedef struct _POW2_HEADER POW2_HEADER;
0052 #define POW2_MAX_COUNT ((0x1000 - sizeof(POW2_HEADER)) >> 2)
0053
0054 static POW2_HEADER *pow2_table[POW2_TABLE_LEN];
0055
0056 static uint32 *pow2_used_table;
0057
0058 static uint32 pow2_used_count, pow2_used_table_pages;
0059
0060 static spinlock pow2_lock = SPINLOCK_INIT;
0061
0062 static void
0063 pow2_add_free_block (uint8 * ptr, uint8 index)
0064 {
0065 POW2_HEADER *hdr = pow2_table[index - POW2_MIN_POW];
0066
0067 for (;;) {
0068 if (hdr->count < POW2_MAX_COUNT) {
0069
0070 hdr->ptrs[hdr->count++] = ptr;
0071 return;
0072 } else {
0073
0074 if (hdr->next) {
0075
0076 hdr = hdr->next;
0077 } else {
0078
0079 hdr->next = map_virtual_page (alloc_phys_frame () | 3);
0080 memset (hdr->next, 0, 0x1000);
0081 hdr = hdr->next;
0082 }
0083 }
0084 }
0085 }
0086
0087
0088
0089
0090 static uint32 pow2_tmp_phys_frames[POW2_MAX_POW_FRAMES];
0091
0092 static uint8 *
0093 pow2_get_free_block (uint8 index)
0094 {
0095 POW2_HEADER *hdr = pow2_table[index - POW2_MIN_POW], *prev = NULL;
0096 uint8 *ptr;
0097
0098 for (;;) {
0099 if (hdr->count == 0) {
0100
0101
0102 if (index < POW2_MAX_POW) {
0103 uint8 *ptr1, *ptr2;
0104
0105
0106
0107
0108 ptr1 = pow2_get_free_block (index + 1);
0109 ptr2 = ptr1 + (1 << (index));
0110
0111 pow2_add_free_block (ptr1, index);
0112
0113
0114
0115
0116
0117 return ptr2;
0118 } else {
0119
0120 int i;
0121 for (i = 0; i < POW2_MAX_POW_FRAMES; i++)
0122 pow2_tmp_phys_frames[i] = alloc_phys_frame () | 3;
0123 return map_virtual_pages (pow2_tmp_phys_frames, POW2_MAX_POW_FRAMES);
0124 }
0125 } else if (hdr->count < POW2_MAX_COUNT || hdr->next == NULL) {
0126
0127 ptr = hdr->ptrs[--hdr->count];
0128 if (prev && hdr->count == 0) {
0129
0130 uint32 frame = (uint32) get_phys_addr ((void *) hdr);
0131 prev->next = NULL;
0132 unmap_virtual_page ((void *) hdr);
0133 free_phys_frame (frame);
0134 }
0135 return ptr;
0136 } else {
0137
0138
0139 prev = hdr;
0140 hdr = hdr->next;
0141 }
0142 }
0143 }
0144
0145 static void
0146 pow2_insert_used_table (uint8 * ptr, uint8 index)
0147 {
0148 if (pow2_used_count >= (pow2_used_table_pages * 0x400)) {
0149 uint32 count = pow2_used_table_pages + 1;
0150 uint32 frames = alloc_phys_frames (count), old_frames;
0151 void *virt = map_contiguous_virtual_pages (frames | 3, count);
0152 memcpy (virt, pow2_used_table, sizeof (uint32) * pow2_used_count);
0153 old_frames = (uint32) get_phys_addr (pow2_used_table);
0154 unmap_virtual_pages ((void *) pow2_used_table, pow2_used_table_pages);
0155 free_phys_frames (old_frames, pow2_used_table_pages);
0156 pow2_used_table = (uint32 *) virt;
0157 pow2_used_table_pages = count;
0158 }
0159 pow2_used_table[pow2_used_count++] = (uint32) ptr | (uint32) index;
0160 }
0161
0162 static int
0163 pow2_remove_used_table (uint8 * ptr, uint8 * index)
0164 {
0165 int i;
0166 for (i = 0; i < pow2_used_count; i++) {
0167 if ((uint32) ptr == (pow2_used_table[i] & (~POW2_MASK_POW))) {
0168
0169 *index = pow2_used_table[i] & POW2_MASK_POW;
0170 pow2_used_table[i] = pow2_used_table[--pow2_used_count];
0171 pow2_used_table[pow2_used_count] = 0;
0172 return 0;
0173 }
0174 }
0175 return -1;
0176 }
0177
0178 static uint8
0179 pow2_compute_index (uint32 size)
0180 {
0181 int i;
0182 if (size <= POW2_MIN_SIZE)
0183 return POW2_MIN_POW;
0184 else if (size >= POW2_MAX_SIZE)
0185 return POW2_MAX_POW;
0186 else {
0187 size--;
0188
0189 asm volatile ("bsrl %1,%0":"=r" (i):"r" (size));
0190 return (i + 1);
0191 }
0192 }
0193
0194 int
0195 pow2_alloc (uint32 size, uint8 ** ptr)
0196 {
0197 uint8 index = pow2_compute_index (size);
0198 spinlock_lock (&pow2_lock);
0199 *ptr = pow2_get_free_block (index);
0200 pow2_insert_used_table (*ptr, index);
0201 spinlock_unlock (&pow2_lock);
0202 memset (*ptr, 0, size);
0203 return index;
0204 }
0205
0206 void
0207 pow2_free (uint8 * ptr)
0208 {
0209 uint8 index;
0210 spinlock_lock (&pow2_lock);
0211 if (pow2_remove_used_table (ptr, &index) == 0) {
0212 pow2_add_free_block (ptr, index);
0213 }
0214 spinlock_unlock (&pow2_lock);
0215 }
0216
0217 void
0218 pow2_init (void)
0219 {
0220 int i;
0221 for (i = 0; i < POW2_TABLE_LEN; i++) {
0222 pow2_table[i] = map_virtual_page (alloc_phys_frame () | 3);
0223 memset (pow2_table[i], 0, 0x1000);
0224 }
0225 pow2_used_table = map_virtual_page (alloc_phys_frame () | 3);
0226 memset (pow2_used_table, 0, 0x1000);
0227 pow2_used_count = 0;
0228 pow2_used_table_pages = 1;
0229 }
0230
0231
0232
0233
0234
0235
0236
0237
0238
0239
0240