[POWERPC] Fix rheap alignment problem
[linux-3.10.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/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_align(rh_info_t * info, int size, int alignment, 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, (must be power of two) */
434         if (size <= 0 || (alignment & (alignment - 1)) != 0)
435                 return ERR_PTR(-EINVAL);
436
437         /* given alignment larger that default rheap alignment */
438         if (alignment > info->alignment)
439                 size += alignment - 1;
440
441         /* Align to configured alignment */
442         size = (size + (info->alignment - 1)) & ~(info->alignment - 1);
443
444         if (assure_empty(info, 1) < 0)
445                 return ERR_PTR(-ENOMEM);
446
447         blk = NULL;
448         list_for_each(l, &info->free_list) {
449                 blk = list_entry(l, rh_block_t, list);
450                 if (size <= blk->size)
451                         break;
452                 blk = NULL;
453         }
454
455         if (blk == NULL)
456                 return ERR_PTR(-ENOMEM);
457
458         /* Just fits */
459         if (blk->size == size) {
460                 /* Move from free list to taken list */
461                 list_del(&blk->list);
462                 blk->owner = owner;
463                 start = blk->start;
464
465                 attach_taken_block(info, blk);
466
467                 return start;
468         }
469
470         newblk = get_slot(info);
471         newblk->start = blk->start;
472         newblk->size = size;
473         newblk->owner = owner;
474
475         /* blk still in free list, with updated start, size */
476         blk->start = (int8_t *)blk->start + size;
477         blk->size -= size;
478
479         start = newblk->start;
480
481         attach_taken_block(info, newblk);
482
483         /* for larger alignment return fixed up pointer  */
484         /* this is no problem with the deallocator since */
485         /* we scan for pointers that lie in the blocks   */
486         if (alignment > info->alignment)
487                 start = (void *)(((unsigned long)start + alignment - 1) &
488                                 ~(alignment - 1));
489
490         return start;
491 }
492
493 void *rh_alloc(rh_info_t * info, int size, const char *owner)
494 {
495         return rh_alloc_align(info, size, info->alignment, owner);
496 }
497
498 /* allocate at precisely the given address */
499 void *rh_alloc_fixed(rh_info_t * info, void *start, int size, const char *owner)
500 {
501         struct list_head *l;
502         rh_block_t *blk, *newblk1, *newblk2;
503         unsigned long s, e, m, bs = 0, be = 0;
504
505         /* Validate size */
506         if (size <= 0)
507                 return ERR_PTR(-EINVAL);
508
509         /* The region must be aligned */
510         s = (unsigned long)start;
511         e = s + size;
512         m = info->alignment - 1;
513
514         /* Round start up */
515         s = (s + m) & ~m;
516
517         /* Round end down */
518         e = e & ~m;
519
520         if (assure_empty(info, 2) < 0)
521                 return ERR_PTR(-ENOMEM);
522
523         blk = NULL;
524         list_for_each(l, &info->free_list) {
525                 blk = list_entry(l, rh_block_t, list);
526                 /* The range must lie entirely inside one free block */
527                 bs = (unsigned long)blk->start;
528                 be = (unsigned long)blk->start + blk->size;
529                 if (s >= bs && e <= be)
530                         break;
531         }
532
533         if (blk == NULL)
534                 return ERR_PTR(-ENOMEM);
535
536         /* Perfect fit */
537         if (bs == s && be == e) {
538                 /* Move from free list to taken list */
539                 list_del(&blk->list);
540                 blk->owner = owner;
541
542                 start = blk->start;
543                 attach_taken_block(info, blk);
544
545                 return start;
546
547         }
548
549         /* blk still in free list, with updated start and/or size */
550         if (bs == s || be == e) {
551                 if (bs == s)
552                         blk->start = (int8_t *)blk->start + size;
553                 blk->size -= size;
554
555         } else {
556                 /* The front free fragment */
557                 blk->size = s - bs;
558
559                 /* The back free fragment */
560                 newblk2 = get_slot(info);
561                 newblk2->start = (void *)e;
562                 newblk2->size = be - e;
563
564                 list_add(&newblk2->list, &blk->list);
565         }
566
567         newblk1 = get_slot(info);
568         newblk1->start = (void *)s;
569         newblk1->size = e - s;
570         newblk1->owner = owner;
571
572         start = newblk1->start;
573         attach_taken_block(info, newblk1);
574
575         return start;
576 }
577
578 int rh_free(rh_info_t * info, void *start)
579 {
580         rh_block_t *blk, *blk2;
581         struct list_head *l;
582         int size;
583
584         /* Linear search for block */
585         blk = NULL;
586         list_for_each(l, &info->taken_list) {
587                 blk2 = list_entry(l, rh_block_t, list);
588                 if (start < blk2->start)
589                         break;
590                 blk = blk2;
591         }
592
593         if (blk == NULL || start > (blk->start + blk->size))
594                 return -EINVAL;
595
596         /* Remove from taken list */
597         list_del(&blk->list);
598
599         /* Get size of freed block */
600         size = blk->size;
601         attach_free_block(info, blk);
602
603         return size;
604 }
605
606 int rh_get_stats(rh_info_t * info, int what, int max_stats, rh_stats_t * stats)
607 {
608         rh_block_t *blk;
609         struct list_head *l;
610         struct list_head *h;
611         int nr;
612
613         switch (what) {
614
615         case RHGS_FREE:
616                 h = &info->free_list;
617                 break;
618
619         case RHGS_TAKEN:
620                 h = &info->taken_list;
621                 break;
622
623         default:
624                 return -EINVAL;
625         }
626
627         /* Linear search for block */
628         nr = 0;
629         list_for_each(l, h) {
630                 blk = list_entry(l, rh_block_t, list);
631                 if (stats != NULL && nr < max_stats) {
632                         stats->start = blk->start;
633                         stats->size = blk->size;
634                         stats->owner = blk->owner;
635                         stats++;
636                 }
637                 nr++;
638         }
639
640         return nr;
641 }
642
643 int rh_set_owner(rh_info_t * info, void *start, const char *owner)
644 {
645         rh_block_t *blk, *blk2;
646         struct list_head *l;
647         int size;
648
649         /* Linear search for block */
650         blk = NULL;
651         list_for_each(l, &info->taken_list) {
652                 blk2 = list_entry(l, rh_block_t, list);
653                 if (start < blk2->start)
654                         break;
655                 blk = blk2;
656         }
657
658         if (blk == NULL || start > (blk->start + blk->size))
659                 return -EINVAL;
660
661         blk->owner = owner;
662         size = blk->size;
663
664         return size;
665 }
666
667 void rh_dump(rh_info_t * info)
668 {
669         static rh_stats_t st[32];       /* XXX maximum 32 blocks */
670         int maxnr;
671         int i, nr;
672
673         maxnr = sizeof(st) / sizeof(st[0]);
674
675         printk(KERN_INFO
676                "info @0x%p (%d slots empty / %d max)\n",
677                info, info->empty_slots, info->max_blocks);
678
679         printk(KERN_INFO "  Free:\n");
680         nr = rh_get_stats(info, RHGS_FREE, maxnr, st);
681         if (nr > maxnr)
682                 nr = maxnr;
683         for (i = 0; i < nr; i++)
684                 printk(KERN_INFO
685                        "    0x%p-0x%p (%u)\n",
686                        st[i].start, (int8_t *) st[i].start + st[i].size,
687                        st[i].size);
688         printk(KERN_INFO "\n");
689
690         printk(KERN_INFO "  Taken:\n");
691         nr = rh_get_stats(info, RHGS_TAKEN, maxnr, st);
692         if (nr > maxnr)
693                 nr = maxnr;
694         for (i = 0; i < nr; i++)
695                 printk(KERN_INFO
696                        "    0x%p-0x%p (%u) %s\n",
697                        st[i].start, (int8_t *) st[i].start + st[i].size,
698                        st[i].size, st[i].owner != NULL ? st[i].owner : "");
699         printk(KERN_INFO "\n");
700 }
701
702 void rh_dump_blk(rh_info_t * info, rh_block_t * blk)
703 {
704         printk(KERN_INFO
705                "blk @0x%p: 0x%p-0x%p (%u)\n",
706                blk, blk->start, (int8_t *) blk->start + blk->size, blk->size);
707 }