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
8 * Author: Pantelis Antoniou <panto@intracom.gr>
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
15 #include <linux/types.h>
16 #include <linux/errno.h>
17 #include <linux/kernel.h>
19 #include <linux/slab.h>
21 #include <asm/rheap.h>
24 * Fixup a list_head, needed when copying lists. If the pointers fall
25 * between s and e, apply the delta. This assumes that
26 * sizeof(struct list_head *) == sizeof(unsigned long *).
28 static inline void fixup(unsigned long s
, unsigned long e
, int d
,
33 pp
= (unsigned long *)&l
->next
;
34 if (*pp
>= s
&& *pp
< e
)
37 pp
= (unsigned long *)&l
->prev
;
38 if (*pp
>= s
&& *pp
< e
)
42 /* Grow the allocated blocks */
43 static int grow(rh_info_t
* info
, int max_blocks
)
45 rh_block_t
*block
, *blk
;
48 unsigned long blks
, blke
;
50 if (max_blocks
<= info
->max_blocks
)
53 new_blocks
= max_blocks
- info
->max_blocks
;
55 block
= kmalloc(sizeof(rh_block_t
) * max_blocks
, GFP_KERNEL
);
59 if (info
->max_blocks
> 0) {
61 /* copy old block area */
62 memcpy(block
, info
->block
,
63 sizeof(rh_block_t
) * info
->max_blocks
);
65 delta
= (char *)block
- (char *)info
->block
;
67 /* and fixup list pointers */
68 blks
= (unsigned long)info
->block
;
69 blke
= (unsigned long)(info
->block
+ info
->max_blocks
);
71 for (i
= 0, blk
= block
; i
< info
->max_blocks
; i
++, blk
++)
72 fixup(blks
, blke
, delta
, &blk
->list
);
74 fixup(blks
, blke
, delta
, &info
->empty_list
);
75 fixup(blks
, blke
, delta
, &info
->free_list
);
76 fixup(blks
, blke
, delta
, &info
->taken_list
);
78 /* free the old allocated memory */
79 if ((info
->flags
& RHIF_STATIC_BLOCK
) == 0)
84 info
->empty_slots
+= new_blocks
;
85 info
->max_blocks
= max_blocks
;
86 info
->flags
&= ~RHIF_STATIC_BLOCK
;
88 /* add all new blocks to the free list */
89 for (i
= 0, blk
= block
+ info
->max_blocks
; i
< new_blocks
; i
++, blk
++)
90 list_add(&blk
->list
, &info
->empty_list
);
96 * Assure at least the required amount of empty slots. If this function
97 * causes a grow in the block area then all pointers kept to the block
100 static int assure_empty(rh_info_t
* info
, int slots
)
104 /* This function is not meant to be used to grow uncontrollably */
109 if (info
->empty_slots
>= slots
)
112 /* Next 16 sized block */
113 max_blocks
= ((info
->max_blocks
+ slots
) + 15) & ~15;
115 return grow(info
, max_blocks
);
118 static rh_block_t
*get_slot(rh_info_t
* info
)
122 /* If no more free slots, and failure to extend. */
123 /* XXX: You should have called assure_empty before */
124 if (info
->empty_slots
== 0) {
125 printk(KERN_ERR
"rh: out of slots; crash is imminent.\n");
129 /* Get empty slot to use */
130 blk
= list_entry(info
->empty_list
.next
, rh_block_t
, list
);
131 list_del_init(&blk
->list
);
142 static inline void release_slot(rh_info_t
* info
, rh_block_t
* blk
)
144 list_add(&blk
->list
, &info
->empty_list
);
148 static void attach_free_block(rh_info_t
* info
, rh_block_t
* blkn
)
155 unsigned long s
, e
, bs
, be
;
158 /* We assume that they are aligned properly */
160 s
= (unsigned long)blkn
->start
;
163 /* Find the blocks immediately before and after the given one
169 list_for_each(l
, &info
->free_list
) {
170 blk
= list_entry(l
, rh_block_t
, list
);
172 bs
= (unsigned long)blk
->start
;
175 if (next
== NULL
&& s
>= bs
)
184 /* If both are not null, break now */
185 if (before
!= NULL
&& after
!= NULL
)
189 /* Now check if they are really adjacent */
190 if (before
!= NULL
&& s
!= (unsigned long)before
->start
+ before
->size
)
193 if (after
!= NULL
&& e
!= (unsigned long)after
->start
)
196 /* No coalescing; list insert and return */
197 if (before
== NULL
&& after
== NULL
) {
200 list_add(&blkn
->list
, &next
->list
);
202 list_add(&blkn
->list
, &info
->free_list
);
207 /* We don't need it anymore */
208 release_slot(info
, blkn
);
210 /* Grow the before block */
211 if (before
!= NULL
&& after
== NULL
) {
212 before
->size
+= size
;
216 /* Grow the after block backwards */
217 if (before
== NULL
&& after
!= NULL
) {
218 after
->start
= (int8_t *)after
->start
- size
;
223 /* Grow the before block, and release the after block */
224 before
->size
+= size
+ after
->size
;
225 list_del(&after
->list
);
226 release_slot(info
, after
);
229 static void attach_taken_block(rh_info_t
* info
, rh_block_t
* blkn
)
234 /* Find the block immediately before the given one (if any) */
235 list_for_each(l
, &info
->taken_list
) {
236 blk
= list_entry(l
, rh_block_t
, list
);
237 if (blk
->start
> blkn
->start
) {
238 list_add_tail(&blkn
->list
, &blk
->list
);
243 list_add_tail(&blkn
->list
, &info
->taken_list
);
247 * Create a remote heap dynamically. Note that no memory for the blocks
248 * are allocated. It will upon the first allocation
250 rh_info_t
*rh_create(unsigned int alignment
)
254 /* Alignment must be a power of two */
255 if ((alignment
& (alignment
- 1)) != 0)
256 return ERR_PTR(-EINVAL
);
258 info
= kmalloc(sizeof(*info
), GFP_KERNEL
);
260 return ERR_PTR(-ENOMEM
);
262 info
->alignment
= alignment
;
264 /* Initially everything as empty */
266 info
->max_blocks
= 0;
267 info
->empty_slots
= 0;
270 INIT_LIST_HEAD(&info
->empty_list
);
271 INIT_LIST_HEAD(&info
->free_list
);
272 INIT_LIST_HEAD(&info
->taken_list
);
278 * Destroy a dynamically created remote heap. Deallocate only if the areas
281 void rh_destroy(rh_info_t
* info
)
283 if ((info
->flags
& RHIF_STATIC_BLOCK
) == 0 && info
->block
!= NULL
)
286 if ((info
->flags
& RHIF_STATIC_INFO
) == 0)
291 * Initialize in place a remote heap info block. This is needed to support
292 * operation very early in the startup of the kernel, when it is not yet safe
295 void rh_init(rh_info_t
* info
, unsigned int alignment
, int max_blocks
,
301 /* Alignment must be a power of two */
302 if ((alignment
& (alignment
- 1)) != 0)
305 info
->alignment
= alignment
;
307 /* Initially everything as empty */
309 info
->max_blocks
= max_blocks
;
310 info
->empty_slots
= max_blocks
;
311 info
->flags
= RHIF_STATIC_INFO
| RHIF_STATIC_BLOCK
;
313 INIT_LIST_HEAD(&info
->empty_list
);
314 INIT_LIST_HEAD(&info
->free_list
);
315 INIT_LIST_HEAD(&info
->taken_list
);
317 /* Add all new blocks to the free list */
318 for (i
= 0, blk
= block
; i
< max_blocks
; i
++, blk
++)
319 list_add(&blk
->list
, &info
->empty_list
);
322 /* Attach a free memory region, coalesces regions if adjuscent */
323 int rh_attach_region(rh_info_t
* info
, void *start
, int size
)
326 unsigned long s
, e
, m
;
329 /* The region must be aligned */
330 s
= (unsigned long)start
;
332 m
= info
->alignment
- 1;
340 /* Take final values */
344 /* Grow the blocks, if needed */
345 r
= assure_empty(info
, 1);
349 blk
= get_slot(info
);
354 attach_free_block(info
, blk
);
359 /* Detatch given address range, splits free block if needed. */
360 void *rh_detach_region(rh_info_t
* info
, void *start
, int size
)
363 rh_block_t
*blk
, *newblk
;
364 unsigned long s
, e
, m
, bs
, be
;
368 return ERR_PTR(-EINVAL
);
370 /* The region must be aligned */
371 s
= (unsigned long)start
;
373 m
= info
->alignment
- 1;
381 if (assure_empty(info
, 1) < 0)
382 return ERR_PTR(-ENOMEM
);
385 list_for_each(l
, &info
->free_list
) {
386 blk
= list_entry(l
, rh_block_t
, list
);
387 /* The range must lie entirely inside one free block */
388 bs
= (unsigned long)blk
->start
;
389 be
= (unsigned long)blk
->start
+ blk
->size
;
390 if (s
>= bs
&& e
<= be
)
396 return ERR_PTR(-ENOMEM
);
399 if (bs
== s
&& be
== e
) {
400 /* Delete from free list, release slot */
401 list_del(&blk
->list
);
402 release_slot(info
, blk
);
406 /* blk still in free list, with updated start and/or size */
407 if (bs
== s
|| be
== e
) {
409 blk
->start
= (int8_t *)blk
->start
+ size
;
413 /* The front free fragment */
416 /* the back free fragment */
417 newblk
= get_slot(info
);
418 newblk
->start
= (void *)e
;
419 newblk
->size
= be
- e
;
421 list_add(&newblk
->list
, &blk
->list
);
427 void *rh_alloc(rh_info_t
* info
, int size
, const char *owner
)
436 return ERR_PTR(-EINVAL
);
438 /* Align to configured alignment */
439 size
= (size
+ (info
->alignment
- 1)) & ~(info
->alignment
- 1);
441 if (assure_empty(info
, 1) < 0)
442 return ERR_PTR(-ENOMEM
);
445 list_for_each(l
, &info
->free_list
) {
446 blk
= list_entry(l
, rh_block_t
, list
);
447 if (size
<= blk
->size
)
453 return ERR_PTR(-ENOMEM
);
456 if (blk
->size
== size
) {
457 /* Move from free list to taken list */
458 list_del(&blk
->list
);
462 attach_taken_block(info
, blk
);
467 newblk
= get_slot(info
);
468 newblk
->start
= blk
->start
;
470 newblk
->owner
= owner
;
472 /* blk still in free list, with updated start, size */
473 blk
->start
= (int8_t *)blk
->start
+ size
;
476 start
= newblk
->start
;
478 attach_taken_block(info
, newblk
);
483 /* allocate at precisely the given address */
484 void *rh_alloc_fixed(rh_info_t
* info
, void *start
, int size
, const char *owner
)
487 rh_block_t
*blk
, *newblk1
, *newblk2
;
488 unsigned long s
, e
, m
, bs
, be
;
492 return ERR_PTR(-EINVAL
);
494 /* The region must be aligned */
495 s
= (unsigned long)start
;
497 m
= info
->alignment
- 1;
505 if (assure_empty(info
, 2) < 0)
506 return ERR_PTR(-ENOMEM
);
509 list_for_each(l
, &info
->free_list
) {
510 blk
= list_entry(l
, rh_block_t
, list
);
511 /* The range must lie entirely inside one free block */
512 bs
= (unsigned long)blk
->start
;
513 be
= (unsigned long)blk
->start
+ blk
->size
;
514 if (s
>= bs
&& e
<= be
)
519 return ERR_PTR(-ENOMEM
);
522 if (bs
== s
&& be
== e
) {
523 /* Move from free list to taken list */
524 list_del(&blk
->list
);
528 attach_taken_block(info
, blk
);
534 /* blk still in free list, with updated start and/or size */
535 if (bs
== s
|| be
== e
) {
537 blk
->start
= (int8_t *)blk
->start
+ size
;
541 /* The front free fragment */
544 /* The back free fragment */
545 newblk2
= get_slot(info
);
546 newblk2
->start
= (void *)e
;
547 newblk2
->size
= be
- e
;
549 list_add(&newblk2
->list
, &blk
->list
);
552 newblk1
= get_slot(info
);
553 newblk1
->start
= (void *)s
;
554 newblk1
->size
= e
- s
;
555 newblk1
->owner
= owner
;
557 start
= newblk1
->start
;
558 attach_taken_block(info
, newblk1
);
563 int rh_free(rh_info_t
* info
, void *start
)
565 rh_block_t
*blk
, *blk2
;
569 /* Linear search for block */
571 list_for_each(l
, &info
->taken_list
) {
572 blk2
= list_entry(l
, rh_block_t
, list
);
573 if (start
< blk2
->start
)
578 if (blk
== NULL
|| start
> (blk
->start
+ blk
->size
))
581 /* Remove from taken list */
582 list_del(&blk
->list
);
584 /* Get size of freed block */
586 attach_free_block(info
, blk
);
591 int rh_get_stats(rh_info_t
* info
, int what
, int max_stats
, rh_stats_t
* stats
)
601 h
= &info
->free_list
;
605 h
= &info
->taken_list
;
612 /* Linear search for block */
614 list_for_each(l
, h
) {
615 blk
= list_entry(l
, rh_block_t
, list
);
616 if (stats
!= NULL
&& nr
< max_stats
) {
617 stats
->start
= blk
->start
;
618 stats
->size
= blk
->size
;
619 stats
->owner
= blk
->owner
;
628 int rh_set_owner(rh_info_t
* info
, void *start
, const char *owner
)
630 rh_block_t
*blk
, *blk2
;
634 /* Linear search for block */
636 list_for_each(l
, &info
->taken_list
) {
637 blk2
= list_entry(l
, rh_block_t
, list
);
638 if (start
< blk2
->start
)
643 if (blk
== NULL
|| start
> (blk
->start
+ blk
->size
))
652 void rh_dump(rh_info_t
* info
)
654 static rh_stats_t st
[32]; /* XXX maximum 32 blocks */
658 maxnr
= ARRAY_SIZE(st
);
661 "info @0x%p (%d slots empty / %d max)\n",
662 info
, info
->empty_slots
, info
->max_blocks
);
664 printk(KERN_INFO
" Free:\n");
665 nr
= rh_get_stats(info
, RHGS_FREE
, maxnr
, st
);
668 for (i
= 0; i
< nr
; i
++)
671 st
[i
].start
, (int8_t *) st
[i
].start
+ st
[i
].size
,
673 printk(KERN_INFO
"\n");
675 printk(KERN_INFO
" Taken:\n");
676 nr
= rh_get_stats(info
, RHGS_TAKEN
, maxnr
, st
);
679 for (i
= 0; i
< nr
; i
++)
681 " 0x%p-0x%p (%u) %s\n",
682 st
[i
].start
, (int8_t *) st
[i
].start
+ st
[i
].size
,
683 st
[i
].size
, st
[i
].owner
!= NULL
? st
[i
].owner
: "");
684 printk(KERN_INFO
"\n");
687 void rh_dump_blk(rh_info_t
* info
, rh_block_t
* blk
)
690 "blk @0x%p: 0x%p-0x%p (%u)\n",
691 blk
, blk
->start
, (int8_t *) blk
->start
+ blk
->size
, blk
->size
);