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