kernel/mem/pow2.c

0001 /*                    The Quest Operating System
0002  *  Copyright (C) 2005-2010  Richard West, Boston University
0003  *
0004  *  This program is free software: you can redistribute it and/or modify
0005  *  it under the terms of the GNU General Public License as published by
0006  *  the Free Software Foundation, either version 3 of the License, or
0007  *  (at your option) any later version.
0008  *
0009  *  This program is distributed in the hope that it will be useful,
0010  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
0011  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
0012  *  GNU General Public License for more details.
0013  *
0014  *  You should have received a copy of the GNU General Public License
0015  *  along with this program.  If not, see <http://www.gnu.org/licenses/>.
0016  */
0017
0018 #include "kernel.h"
0019 #include "mem/mem.h"
0020 #include "smp/spinlock.h"
0021
0022 /* power-of-2 memory allocator works with blocks in increasing sizes
0023  * in powers of 2, from 2^POW2_MIN_POW to 2^POW2_MAX_POW */
0024
0025 #define POW2_MIN_POW 5
0026 #define POW2_MAX_POW 16
0027 /* NB: the value of POW2_MAX_POW has to be smaller than 2^POW2_MIN_POW
0028  * because it needs to be able to fit within the POW2_MASK_POW.  Also
0029  * keep in mind it needs to be able to find a contiguous virtual
0030  * address range every time it allocates one of these large
0031  * blocks. */
0032
0033 #define POW2_MIN_SIZE (1<<POW2_MIN_POW)
0034 #define POW2_MAX_SIZE (1<<POW2_MAX_POW)
0035
0036 /* Length of the central header table */
0037 #define POW2_TABLE_LEN ((POW2_MAX_POW - POW2_MIN_POW)+1)
0038
0039 /* How many frames to allocate for a max-size block: */
0040 #define POW2_MAX_POW_FRAMES (1 << (POW2_MAX_POW - 12))
0041
0042 /* Mask the index from a descriptor: */
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; /* array of descriptors:
0057                                  * pointer | index */
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       /* There is room in the current header's block */
0070       hdr->ptrs[hdr->count++] = ptr;
0071       return;
0072     } else {
0073       /* There is not enough room */
0074       if (hdr->next) {
0075         /* Chase the next pointer */
0076         hdr = hdr->next;
0077       } else {
0078         /* End of the list -- make a new header */
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 /* Trying to avoid making the frame-size of pow2_get_free_block any
0088  * larger than it is -- because of recursion -- and this is used in a
0089  * re-entrantly safe fashion. */
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       /* no free blocks -- get one */
0101       /* hdr->count can only be 0 for first in chain */
0102       if (index < POW2_MAX_POW) {
0103         uint8 *ptr1, *ptr2;
0104
0105         /* Recursive call: 32 bytes per frame, 11 calls deep, 352
0106          * bytes of stack worst-case.  Should be acceptable, for
0107          * now. */
0108         ptr1 = pow2_get_free_block (index + 1);
0109         ptr2 = ptr1 + (1 << (index));
0110
0111         pow2_add_free_block (ptr1, index);
0112
0113         /* It is safe to return ptr2 here because if there were no
0114          * free blocks upon entering this section of code, then there
0115          * is no need to check 'prev' and possibly zero its next
0116          * pointer. */
0117         return ptr2;
0118       } else {
0119         /* grab new pages */
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       /* There are free blocks ready to go */
0127       ptr = hdr->ptrs[--hdr->count];
0128       if (prev && hdr->count == 0) {
0129         /* We followed a next pointer to get here. */
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       /* hdr->count == POW2_MAX_COUNT && hdr->next != NULL */
0138       /* chase next pointer and try to use that header instead */
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       /* found it */
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     /* bit scan reverse -- find most significant set bit */
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  * Local Variables:
0233  * indent-tabs-mode: nil
0234  * mode: C
0235  * c-file-style: "gnu"
0236  * c-basic-offset: 2
0237  * End:
0238  */
0239
0240 /* vi: set et sw=2 sts=2: */