Merge nommu tree
[linux-2.6] / arch / powerpc / lib / rheap.c
1 /*
2  * A Remote Heap.  Remote means that we don't touch the memory that the
3  * heap points to. Normal heap implementations use the memory they manage
4  * to place their list. We cannot do that because the memory we manage may
5  * have special properties, for example it is uncachable or of different
6  * endianess.
7  *
8  * Author: Pantelis Antoniou <panto@intracom.gr>
9  *
10  * 2004 (c) INTRACOM S.A. Greece. This file is licensed under
11  * the terms of the GNU General Public License version 2. This program
12  * is licensed "as is" without any warranty of any kind, whether express
13  * or implied.
14  */
15 #include <linux/types.h>
16 #include <linux/errno.h>
17 #include <linux/mm.h>
18 #include <linux/slab.h>
19
20 #include <asm/rheap.h>
21
22 /*
23  * Fixup a list_head, needed when copying lists.  If the pointers fall
24  * between s and e, apply the delta.  This assumes that
25  * sizeof(struct list_head *) == sizeof(unsigned long *).
26  */
27 static inline void fixup(unsigned long s, unsigned long e, int d,
28                          struct list_head *l)
29 {
30         unsigned long *pp;
31
32         pp = (unsigned long *)&l->next;
33         if (*pp >= s && *pp < e)
34                 *pp += d;
35
36         pp = (unsigned long *)&l->prev;
37         if (*pp >= s && *pp < e)
38                 *pp += d;
39 }
40
41 /* Grow the allocated blocks */
42 static int grow(rh_info_t * info, int max_blocks)
43 {
44         rh_block_t *block, *blk;
45         int i, new_blocks;
46         int delta;
47         unsigned long blks, blke;
48
49         if (max_blocks <= info->max_blocks)
50                 return -EINVAL;
51
52         new_blocks = max_blocks - info->max_blocks;
53
54         block = kmalloc(sizeof(rh_block_t) * max_blocks, GFP_KERNEL);
55         if (block == NULL)
56                 return -ENOMEM;
57
58         if (info->max_blocks > 0) {
59
60                 /* copy old block area */
61                 memcpy(block, info->block,
62                        sizeof(rh_block_t) * info->max_blocks);
63
64                 delta = (char *)block - (char *)info->block;
65
66                 /* and fixup list pointers */
67                 blks = (unsigned long)info->block;
68                 blke = (unsigned long)(info->block + info->max_blocks);
69
70                 for (i = 0, blk = block; i < info->max_blocks; i++, blk++)
71                         fixup(blks, blke, delta, &blk->list);
72
73                 fixup(blks, blke, delta, &info->empty_list);
74                 fixup(blks, blke, delta, &info->free_list);
75                 fixup(blks, blke, delta, &info->taken_list);
76
77                 /* free the old allocated memory */
78                 if ((info->flags & RHIF_STATIC_BLOCK) == 0)
79                         kfree(info->block);
80         }
81
82         info->block = block;
83         info->empty_slots += new_blocks;
84         info->max_blocks = max_blocks;
85         info->flags &= ~RHIF_STATIC_BLOCK;
86
87         /* add all new blocks to the free list */
88         for (i = 0, blk = block + info->max_blocks; i < new_blocks; i++, blk++)
89                 list_add(&blk->list, &info->empty_list);
90
91         return 0;
92 }
93
94 /*
95  * Assure at least the required amount of empty slots.  If this function
96  * causes a grow in the block area then all pointers kept to the block
97  * area are invalid!
98  */
99 static int assure_empty(rh_info_t * info, int slots)
100 {
101         int max_blocks;
102
103         /* This function is not meant to be used to grow uncontrollably */
104         if (slots >= 4)
105                 return -EINVAL;
106
107         /* Enough space */
108         if (info->empty_slots >= slots)
109                 return 0;
110
111         /* Next 16 sized block */
112         max_blocks = ((info->max_blocks + slots) + 15) & ~15;
113
114         return grow(info, max_blocks);
115 }
116
117 static rh_block_t *get_slot(rh_info_t * info)
118 {
119         rh_block_t *blk;
120
121         /* If no more free slots, and failure to extend. */
122         /* XXX: You should have called assure_empty before */
123         if (info->empty_slots == 0) {
124                 printk(KERN_ERR "rh: out of slots; crash is imminent.\n");
125                 return NULL;
126         }
127
128         /* Get empty slot to use */
129         blk = list_entry(info->empty_list.next, rh_block_t, list);
130         list_del_init(&blk->list);
131         info->empty_slots--;
132
133         /* Initialize */
134         blk->start = NULL;
135         blk->size = 0;
136         blk->owner = NULL;
137
138         return blk;
139 }
140
141 static inline void release_slot(rh_info_t * info, rh_block_t * blk)
142 {
143         list_add(&blk->list, &info->empty_list);
144         info->empty_slots++;
145 }
146
147 static void attach_free_block(rh_info_t * info, rh_block_t * blkn)
148 {
149         rh_block_t *blk;
150         rh_block_t *before;
151         rh_block_t *after;
152         rh_block_t *next;
153         int size;
154         unsigned long s, e, bs, be;
155         struct list_head *l;
156
157         /* We assume that they are aligned properly */
158         size = blkn->size;
159         s = (unsigned long)blkn->start;
160         e = s + size;
161
162         /* Find the blocks immediately before and after the given one
163          * (if any) */
164         before = NULL;
165         after = NULL;
166         next = NULL;
167
168         list_for_each(l, &info->free_list) {
169                 blk = list_entry(l, rh_block_t, list);
170
171                 bs = (unsigned long)blk->start;
172                 be = bs + blk->size;
173
174                 if (next == NULL && s >= bs)
175                         next = blk;
176
177                 if (be == s)
178                         before = blk;
179
180                 if (e == bs)
181                         after = blk;
182
183                 /* If both are not null, break now */
184                 if (before != NULL && after != NULL)
185                         break;
186         }
187
188         /* Now check if they are really adjacent */
189         if (before != NULL && s != (unsigned long)before->start + before->size)
190                 before = NULL;
191
192         if (after != NULL && e != (unsigned long)after->start)
193                 after = NULL;
194
195         /* No coalescing; list insert and return */
196         if (before == NULL && after == NULL) {
197
198                 if (next != NULL)
199                         list_add(&blkn->list, &next->list);
200                 else
201                         list_add(&blkn->list, &info->free_list);
202
203                 return;
204         }
205
206         /* We don't need it anymore */
207         release_slot(info, blkn);
208
209         /* Grow the before block */
210         if (before != NULL && after == NULL) {
211                 before->size += size;
212                 return;
213         }
214
215         /* Grow the after block backwards */
216         if (before == NULL && after != NULL) {
217                 after->start = (int8_t *)after->start - size;
218                 after->size += size;
219                 return;
220         }
221
222         /* Grow the before block, and release the after block */
223         before->size += size + after->size;
224         list_del(&after->list);
225         release_slot(info, after);
226 }
227
228 static void attach_taken_block(rh_info_t * info, rh_block_t * blkn)
229 {
230         rh_block_t *blk;
231         struct list_head *l;
232
233         /* Find the block immediately before the given one (if any) */
234         list_for_each(l, &info->taken_list) {
235                 blk = list_entry(l, rh_block_t, list);
236                 if (blk->start > blkn->start) {
237                         list_add_tail(&blkn->list, &blk->list);
238                         return;
239                 }
240         }
241
242         list_add_tail(&blkn->list, &info->taken_list);
243 }
244
245 /*
246  * Create a remote heap dynamically.  Note that no memory for the blocks
247  * are allocated.  It will upon the first allocation
248  */
249 rh_info_t *rh_create(unsigned int alignment)
250 {
251         rh_info_t *info;
252
253         /* Alignment must be a power of two */
254         if ((alignment & (alignment - 1)) != 0)
255                 return ERR_PTR(-EINVAL);
256
257         info = kmalloc(sizeof(*info), GFP_KERNEL);
258         if (info == NULL)
259                 return ERR_PTR(-ENOMEM);
260
261         info->alignment = alignment;
262
263         /* Initially everything as empty */
264         info->block = NULL;
265         info->max_blocks = 0;
266         info->empty_slots = 0;
267         info->flags = 0;
268
269         INIT_LIST_HEAD(&info->empty_list);
270         INIT_LIST_HEAD(&info->free_list);
271         INIT_LIST_HEAD(&info->taken_list);
272
273         return info;
274 }
275
276 /*
277  * Destroy a dynamically created remote heap.  Deallocate only if the areas
278  * are not static
279  */
280 void rh_destroy(rh_info_t * info)
281 {
282         if ((info->flags & RHIF_STATIC_BLOCK) == 0 && info->block != NULL)
283                 kfree(info->block);
284
285         if ((info->flags & RHIF_STATIC_INFO) == 0)
286                 kfree(info);
287 }
288
289 /*
290  * Initialize in place a remote heap info block.  This is needed to support
291  * operation very early in the startup of the kernel, when it is not yet safe
292  * to call kmalloc.
293  */
294 void rh_init(rh_info_t * info, unsigned int alignment, int max_blocks,
295              rh_block_t * block)
296 {
297         int i;
298         rh_block_t *blk;
299
300         /* Alignment must be a power of two */
301         if ((alignment & (alignment - 1)) != 0)
302                 return;
303
304         info->alignment = alignment;
305
306         /* Initially everything as empty */
307         info->block = block;
308         info->max_blocks = max_blocks;
309         info->empty_slots = max_blocks;
310         info->flags = RHIF_STATIC_INFO | RHIF_STATIC_BLOCK;
311
312         INIT_LIST_HEAD(&info->empty_list);
313         INIT_LIST_HEAD(&info->free_list);
314         INIT_LIST_HEAD(&info->taken_list);
315
316         /* Add all new blocks to the free list */
317         for (i = 0, blk = block; i < max_blocks; i++, blk++)
318                 list_add(&blk->list, &info->empty_list);
319 }
320
321 /* Attach a free memory region, coalesces regions if adjuscent */
322 int rh_attach_region(rh_info_t * info, void *start, int size)
323 {
324         rh_block_t *blk;
325         unsigned long s, e, m;
326         int r;
327
328         /* The region must be aligned */
329         s = (unsigned long)start;
330         e = s + size;
331         m = info->alignment - 1;
332
333         /* Round start up */
334         s = (s + m) & ~m;
335
336         /* Round end down */
337         e = e & ~m;
338
339         /* Take final values */
340         start = (void *)s;
341         size = (int)(e - s);
342
343         /* Grow the blocks, if needed */
344         r = assure_empty(info, 1);
345         if (r < 0)
346                 return r;
347
348         blk = get_slot(info);
349         blk->start = start;
350         blk->size = size;
351         blk->owner = NULL;
352
353         attach_free_block(info, blk);
354
355         return 0;
356 }
357
358 /* Detatch given address range, splits free block if needed. */
359 void *rh_detach_region(rh_info_t * info, void *start, int size)
360 {
361         struct list_head *l;
362         rh_block_t *blk, *newblk;
363         unsigned long s, e, m, bs, be;
364
365         /* Validate size */
366         if (size <= 0)
367                 return ERR_PTR(-EINVAL);
368
369         /* The region must be aligned */
370         s = (unsigned long)start;
371         e = s + size;
372         m = info->alignment - 1;
373
374         /* Round start up */
375         s = (s + m) & ~m;
376
377         /* Round end down */
378         e = e & ~m;
379
380         if (assure_empty(info, 1) < 0)
381                 return ERR_PTR(-ENOMEM);
382
383         blk = NULL;
384         list_for_each(l, &info->free_list) {
385                 blk = list_entry(l, rh_block_t, list);
386                 /* The range must lie entirely inside one free block */
387                 bs = (unsigned long)blk->start;
388                 be = (unsigned long)blk->start + blk->size;
389                 if (s >= bs && e <= be)
390                         break;
391                 blk = NULL;
392         }
393
394         if (blk == NULL)
395                 return ERR_PTR(-ENOMEM);
396
397         /* Perfect fit */
398         if (bs == s && be == e) {
399                 /* Delete from free list, release slot */
400                 list_del(&blk->list);
401                 release_slot(info, blk);
402                 return (void *)s;
403         }
404
405         /* blk still in free list, with updated start and/or size */
406         if (bs == s || be == e) {
407                 if (bs == s)
408                         blk->start = (int8_t *)blk->start + size;
409                 blk->size -= size;
410
411         } else {
412                 /* The front free fragment */
413                 blk->size = s - bs;
414
415                 /* the back free fragment */
416                 newblk = get_slot(info);
417                 newblk->start = (void *)e;
418                 newblk->size = be - e;
419
420                 list_add(&newblk->list, &blk->list);
421         }
422
423         return (void *)s;
424 }
425
426 void *rh_alloc(rh_info_t * info, int size, const char *owner)
427 {
428         struct list_head *l;
429         rh_block_t *blk;
430         rh_block_t *newblk;
431         void *start;
432
433         /* Validate size */
434         if (size <= 0)
435                 return ERR_PTR(-EINVAL);
436
437         /* Align to configured alignment */
438         size = (size + (info->alignment - 1)) & ~(info->alignment - 1);
439
440         if (assure_empty(info, 1) < 0)
441                 return ERR_PTR(-ENOMEM);
442
443         blk = NULL;
444         list_for_each(l, &info->free_list) {
445                 blk = list_entry(l, rh_block_t, list);
446                 if (size <= blk->size)
447                         break;
448                 blk = NULL;
449         }
450
451         if (blk == NULL)
452                 return ERR_PTR(-ENOMEM);
453
454         /* Just fits */
455         if (blk->size == size) {
456                 /* Move from free list to taken list */
457                 list_del(&blk->list);
458                 blk->owner = owner;
459                 start = blk->start;
460
461                 attach_taken_block(info, blk);
462
463                 return start;
464         }
465
466         newblk = get_slot(info);
467         newblk->start = blk->start;
468         newblk->size = size;
469         newblk->owner = owner;
470
471         /* blk still in free list, with updated start, size */
472         blk->start = (int8_t *)blk->start + size;
473         blk->size -= size;
474
475         start = newblk->start;
476
477         attach_taken_block(info, newblk);
478
479         return start;
480 }
481
482 /* allocate at precisely the given address */
483 void *rh_alloc_fixed(rh_info_t * info, void *start, int size, const char *owner)
484 {
485         struct list_head *l;
486         rh_block_t *blk, *newblk1, *newblk2;
487         unsigned long s, e, m, bs, be;
488
489         /* Validate size */
490         if (size <= 0)
491                 return ERR_PTR(-EINVAL);
492
493         /* The region must be aligned */
494         s = (unsigned long)start;
495         e = s + size;
496         m = info->alignment - 1;
497
498         /* Round start up */
499         s = (s + m) & ~m;
500
501         /* Round end down */
502         e = e & ~m;
503
504         if (assure_empty(info, 2) < 0)
505                 return ERR_PTR(-ENOMEM);
506
507         blk = NULL;
508         list_for_each(l, &info->free_list) {
509                 blk = list_entry(l, rh_block_t, list);
510                 /* The range must lie entirely inside one free block */
511                 bs = (unsigned long)blk->start;
512                 be = (unsigned long)blk->start + blk->size;
513                 if (s >= bs && e <= be)
514                         break;
515         }
516
517         if (blk == NULL)
518                 return ERR_PTR(-ENOMEM);
519
520         /* Perfect fit */
521         if (bs == s && be == e) {
522                 /* Move from free list to taken list */
523                 list_del(&blk->list);
524                 blk->owner = owner;
525
526                 start = blk->start;
527                 attach_taken_block(info, blk);
528
529                 return start;
530
531         }
532
533         /* blk still in free list, with updated start and/or size */
534         if (bs == s || be == e) {
535                 if (bs == s)
536                         blk->start = (int8_t *)blk->start + size;
537                 blk->size -= size;
538
539         } else {
540                 /* The front free fragment */
541                 blk->size = s - bs;
542
543                 /* The back free fragment */
544                 newblk2 = get_slot(info);
545                 newblk2->start = (void *)e;
546                 newblk2->size = be - e;
547
548                 list_add(&newblk2->list, &blk->list);
549         }
550
551         newblk1 = get_slot(info);
552         newblk1->start = (void *)s;
553         newblk1->size = e - s;
554         newblk1->owner = owner;
555
556         start = newblk1->start;
557         attach_taken_block(info, newblk1);
558
559         return start;
560 }
561
562 int rh_free(rh_info_t * info, void *start)
563 {
564         rh_block_t *blk, *blk2;
565         struct list_head *l;
566         int size;
567
568         /* Linear search for block */
569         blk = NULL;
570         list_for_each(l, &info->taken_list) {
571                 blk2 = list_entry(l, rh_block_t, list);
572                 if (start < blk2->start)
573                         break;
574                 blk = blk2;
575         }
576
577         if (blk == NULL || start > (blk->start + blk->size))
578                 return -EINVAL;
579
580         /* Remove from taken list */
581         list_del(&blk->list);
582
583         /* Get size of freed block */
584         size = blk->size;
585         attach_free_block(info, blk);
586
587         return size;
588 }
589
590 int rh_get_stats(rh_info_t * info, int what, int max_stats, rh_stats_t * stats)
591 {
592         rh_block_t *blk;
593         struct list_head *l;
594         struct list_head *h;
595         int nr;
596
597         switch (what) {
598
599         case RHGS_FREE:
600                 h = &info->free_list;
601                 break;
602
603         case RHGS_TAKEN:
604                 h = &info->taken_list;
605                 break;
606
607         default:
608                 return -EINVAL;
609         }
610
611         /* Linear search for block */
612         nr = 0;
613         list_for_each(l, h) {
614                 blk = list_entry(l, rh_block_t, list);
615                 if (stats != NULL && nr < max_stats) {
616                         stats->start = blk->start;
617                         stats->size = blk->size;
618                         stats->owner = blk->owner;
619                         stats++;
620                 }
621                 nr++;
622         }
623
624         return nr;
625 }
626
627 int rh_set_owner(rh_info_t * info, void *start, const char *owner)
628 {
629         rh_block_t *blk, *blk2;
630         struct list_head *l;
631         int size;
632
633         /* Linear search for block */
634         blk = NULL;
635         list_for_each(l, &info->taken_list) {
636                 blk2 = list_entry(l, rh_block_t, list);
637                 if (start < blk2->start)
638                         break;
639                 blk = blk2;
640         }
641
642         if (blk == NULL || start > (blk->start + blk->size))
643                 return -EINVAL;
644
645         blk->owner = owner;
646         size = blk->size;
647
648         return size;
649 }
650
651 void rh_dump(rh_info_t * info)
652 {
653         static rh_stats_t st[32];       /* XXX maximum 32 blocks */
654         int maxnr;
655         int i, nr;
656
657         maxnr = sizeof(st) / sizeof(st[0]);
658
659         printk(KERN_INFO
660                "info @0x%p (%d slots empty / %d max)\n",
661                info, info->empty_slots, info->max_blocks);
662
663         printk(KERN_INFO "  Free:\n");
664         nr = rh_get_stats(info, RHGS_FREE, maxnr, st);
665         if (nr > maxnr)
666                 nr = maxnr;
667         for (i = 0; i < nr; i++)
668                 printk(KERN_INFO
669                        "    0x%p-0x%p (%u)\n",
670                        st[i].start, (int8_t *) st[i].start + st[i].size,
671                        st[i].size);
672         printk(KERN_INFO "\n");
673
674         printk(KERN_INFO "  Taken:\n");
675         nr = rh_get_stats(info, RHGS_TAKEN, maxnr, st);
676         if (nr > maxnr)
677                 nr = maxnr;
678         for (i = 0; i < nr; i++)
679                 printk(KERN_INFO
680                        "    0x%p-0x%p (%u) %s\n",
681                        st[i].start, (int8_t *) st[i].start + st[i].size,
682                        st[i].size, st[i].owner != NULL ? st[i].owner : "");
683         printk(KERN_INFO "\n");
684 }
685
686 void rh_dump_blk(rh_info_t * info, rh_block_t * blk)
687 {
688         printk(KERN_INFO
689                "blk @0x%p: 0x%p-0x%p (%u)\n",
690                blk, blk->start, (int8_t *) blk->start + blk->size, blk->size);
691 }