arch/ppc64/mm/imalloc.c

   1 /*
   2  * c 2001 PPC 64 Team, IBM Corp
   3  *
   4  *      This program is free software; you can redistribute it and/or
   5  *      modify it under the terms of the GNU General Public License
   6  *      as published by the Free Software Foundation; either version
   7  *      2 of the License, or (at your option) any later version.
   8  */
   9
  10 #include <linux/slab.h>
  11 #include <linux/vmalloc.h>
  12
  13 #include <asm/uaccess.h>
  14 #include <asm/pgalloc.h>
  15 #include <asm/pgtable.h>
  16 #include <asm/semaphore.h>
  17 #include <asm/imalloc.h>
  18
  19 static DECLARE_MUTEX(imlist_sem);
  20 struct vm_struct * imlist = NULL;
  21
  22 static int get_free_im_addr(unsigned long size, unsigned long *im_addr)
  23 {
  24         unsigned long addr;
  25         struct vm_struct **p, *tmp;
  26
  27         addr = ioremap_bot;
  28         for (p = &imlist; (tmp = *p) ; p = &tmp->next) {
  29                 if (size + addr < (unsigned long) tmp->addr)
  30                         break;
  31                 if ((unsigned long)tmp->addr >= ioremap_bot)
  32                         addr = tmp->size + (unsigned long) tmp->addr;
  33                 if (addr > IMALLOC_END-size)
  34                         return 1;
  35         }
  36         *im_addr = addr;
  37
  38         return 0;
  39 }
  40
  41 /* Return whether the region described by v_addr and size is a subset
  42  * of the region described by parent
  43  */
  44 static inline int im_region_is_subset(unsigned long v_addr, unsigned long size,
  45                         struct vm_struct *parent)
  46 {
  47         return (int) (v_addr >= (unsigned long) parent->addr &&
  48                       v_addr < (unsigned long) parent->addr + parent->size &&
  49                       size < parent->size);
  50 }
  51
  52 /* Return whether the region described by v_addr and size is a superset
  53  * of the region described by child
  54  */
  55 static int im_region_is_superset(unsigned long v_addr, unsigned long size,
  56                 struct vm_struct *child)
  57 {
  58         struct vm_struct parent;
  59
  60         parent.addr = (void *) v_addr;
  61         parent.size = size;
  62
  63         return im_region_is_subset((unsigned long) child->addr, child->size,
  64                         &parent);
  65 }
  66
  67 /* Return whether the region described by v_addr and size overlaps
  68  * the region described by vm.  Overlapping regions meet the
  69  * following conditions:
  70  * 1) The regions share some part of the address space
  71  * 2) The regions aren't identical
  72  * 3) Neither region is a subset of the other
  73  */
  74 static int im_region_overlaps(unsigned long v_addr, unsigned long size,
  75                      struct vm_struct *vm)
  76 {
  77         if (im_region_is_superset(v_addr, size, vm))
  78                 return 0;
  79
  80         return (v_addr + size > (unsigned long) vm->addr + vm->size &&
  81                 v_addr < (unsigned long) vm->addr + vm->size) ||
  82                (v_addr < (unsigned long) vm->addr &&
  83                 v_addr + size > (unsigned long) vm->addr);
  84 }
  85
  86 /* Determine imalloc status of region described by v_addr and size.
  87  * Can return one of the following:
  88  * IM_REGION_UNUSED   -  Entire region is unallocated in imalloc space.
  89  * IM_REGION_SUBSET -    Region is a subset of a region that is already
  90  *                       allocated in imalloc space.
  91  *                       vm will be assigned to a ptr to the parent region.
  92  * IM_REGION_EXISTS -    Exact region already allocated in imalloc space.
  93  *                       vm will be assigned to a ptr to the existing imlist
  94  *                       member.
  95  * IM_REGION_OVERLAPS -  Region overlaps an allocated region in imalloc space.
  96  * IM_REGION_SUPERSET -  Region is a superset of a region that is already
  97  *                       allocated in imalloc space.
  98  */
  99 static int im_region_status(unsigned long v_addr, unsigned long size,
 100                     struct vm_struct **vm)
 101 {
 102         struct vm_struct *tmp;
 103
 104         for (tmp = imlist; tmp; tmp = tmp->next)
 105                 if (v_addr < (unsigned long) tmp->addr + tmp->size)
 106                         break;
 107
 108         if (tmp) {
 109                 if (im_region_overlaps(v_addr, size, tmp))
 110                         return IM_REGION_OVERLAP;
 111
 112                 *vm = tmp;
 113                 if (im_region_is_subset(v_addr, size, tmp)) {
 114                         /* Return with tmp pointing to superset */
 115                         return IM_REGION_SUBSET;
 116                 }
 117                 if (im_region_is_superset(v_addr, size, tmp)) {
 118                         /* Return with tmp pointing to first subset */
 119                         return IM_REGION_SUPERSET;
 120                 }
 121                 else if (v_addr == (unsigned long) tmp->addr &&
 122                          size == tmp->size) {
 123                         /* Return with tmp pointing to exact region */
 124                         return IM_REGION_EXISTS;
 125                 }
 126         }
 127
 128         *vm = NULL;
 129         return IM_REGION_UNUSED;
 130 }
 131
 132 static struct vm_struct * split_im_region(unsigned long v_addr,
 133                 unsigned long size, struct vm_struct *parent)
 134 {
 135         struct vm_struct *vm1 = NULL;
 136         struct vm_struct *vm2 = NULL;
 137         struct vm_struct *new_vm = NULL;
 138
 139         vm1 = (struct vm_struct *) kmalloc(sizeof(*vm1), GFP_KERNEL);
 140         if (vm1 == NULL) {
 141                 printk(KERN_ERR "%s() out of memory\n", __FUNCTION__);
 142                 return NULL;
 143         }
 144
 145         if (v_addr == (unsigned long) parent->addr) {
 146                 /* Use existing parent vm_struct to represent child, allocate
 147                  * new one for the remainder of parent range
 148                  */
 149                 vm1->size = parent->size - size;
 150                 vm1->addr = (void *) (v_addr + size);
 151                 vm1->next = parent->next;
 152
 153                 parent->size = size;
 154                 parent->next = vm1;
 155                 new_vm = parent;
 156         } else if (v_addr + size == (unsigned long) parent->addr +
 157                         parent->size) {
 158                 /* Allocate new vm_struct to represent child, use existing
 159                  * parent one for remainder of parent range
 160                  */
 161                 vm1->size = size;
 162                 vm1->addr = (void *) v_addr;
 163                 vm1->next = parent->next;
 164                 new_vm = vm1;
 165
 166                 parent->size -= size;
 167                 parent->next = vm1;
 168         } else {
 169                 /* Allocate two new vm_structs for the new child and
 170                  * uppermost remainder, and use existing parent one for the
 171                  * lower remainder of parent range
 172                  */
 173                 vm2 = (struct vm_struct *) kmalloc(sizeof(*vm2), GFP_KERNEL);
 174                 if (vm2 == NULL) {
 175                         printk(KERN_ERR "%s() out of memory\n", __FUNCTION__);
 176                         kfree(vm1);
 177                         return NULL;
 178                 }
 179
 180                 vm1->size = size;
 181                 vm1->addr = (void *) v_addr;
 182                 vm1->next = vm2;
 183                 new_vm = vm1;
 184
 185                 vm2->size = ((unsigned long) parent->addr + parent->size) -
 186                                 (v_addr + size);
 187                 vm2->addr = (void *) v_addr + size;
 188                 vm2->next = parent->next;
 189
 190                 parent->size = v_addr - (unsigned long) parent->addr;
 191                 parent->next = vm1;
 192         }
 193
 194         return new_vm;
 195 }
 196
 197 static struct vm_struct * __add_new_im_area(unsigned long req_addr,
 198                                             unsigned long size)
 199 {
 200         struct vm_struct **p, *tmp, *area;
 201
 202         for (p = &imlist; (tmp = *p) ; p = &tmp->next) {
 203                 if (req_addr + size <= (unsigned long)tmp->addr)
 204                         break;
 205         }
 206
 207         area = (struct vm_struct *) kmalloc(sizeof(*area), GFP_KERNEL);
 208         if (!area)
 209                 return NULL;
 210         area->flags = 0;
 211         area->addr = (void *)req_addr;
 212         area->size = size;
 213         area->next = *p;
 214         *p = area;
 215
 216         return area;
 217 }
 218
 219 static struct vm_struct * __im_get_area(unsigned long req_addr,
 220                                         unsigned long size,
 221                                         int criteria)
 222 {
 223         struct vm_struct *tmp;
 224         int status;
 225
 226         status = im_region_status(req_addr, size, &tmp);
 227         if ((criteria & status) == 0) {
 228                 return NULL;
 229         }
 230
 231         switch (status) {
 232         case IM_REGION_UNUSED:
 233                 tmp = __add_new_im_area(req_addr, size);
 234                 break;
 235         case IM_REGION_SUBSET:
 236                 tmp = split_im_region(req_addr, size, tmp);
 237                 break;
 238         case IM_REGION_EXISTS:
 239                 /* Return requested region */
 240                 break;
 241         case IM_REGION_SUPERSET:
 242                 /* Return first existing subset of requested region */
 243                 break;
 244         default:
 245                 printk(KERN_ERR "%s() unexpected imalloc region status\n",
 246                                 __FUNCTION__);
 247                 tmp = NULL;
 248         }
 249
 250         return tmp;
 251 }
 252
 253 struct vm_struct * im_get_free_area(unsigned long size)
 254 {
 255         struct vm_struct *area;
 256         unsigned long addr;
 257
 258         down(&imlist_sem);
 259         if (get_free_im_addr(size, &addr)) {
 260                 printk(KERN_ERR "%s() cannot obtain addr for size 0x%lx\n",
 261                                 __FUNCTION__, size);
 262                 area = NULL;
 263                 goto next_im_done;
 264         }
 265
 266         area = __im_get_area(addr, size, IM_REGION_UNUSED);
 267         if (area == NULL) {
 268                 printk(KERN_ERR
 269                        "%s() cannot obtain area for addr 0x%lx size 0x%lx\n",
 270                         __FUNCTION__, addr, size);
 271         }
 272 next_im_done:
 273         up(&imlist_sem);
 274         return area;
 275 }
 276
 277 struct vm_struct * im_get_area(unsigned long v_addr, unsigned long size,
 278                 int criteria)
 279 {
 280         struct vm_struct *area;
 281
 282         down(&imlist_sem);
 283         area = __im_get_area(v_addr, size, criteria);
 284         up(&imlist_sem);
 285         return area;
 286 }
 287
 288 unsigned long im_free(void * addr)
 289 {
 290         struct vm_struct **p, *tmp;
 291         unsigned long ret_size = 0;
 292
 293         if (!addr)
 294                 return ret_size;
 295         if ((PAGE_SIZE-1) & (unsigned long) addr) {
 296                 printk(KERN_ERR "Trying to %s bad address (%p)\n", __FUNCTION__,                        addr);
 297                 return ret_size;
 298         }
 299         down(&imlist_sem);
 300         for (p = &imlist ; (tmp = *p) ; p = &tmp->next) {
 301                 if (tmp->addr == addr) {
 302                         ret_size = tmp->size;
 303                         *p = tmp->next;
 304                         kfree(tmp);
 305                         up(&imlist_sem);
 306                         return ret_size;
 307                 }
 308         }
 309         up(&imlist_sem);
 310         printk(KERN_ERR "Trying to %s nonexistent area (%p)\n", __FUNCTION__,
 311                         addr);
 312         return ret_size;
 313 }