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