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