Rev 2106 | Only display areas with differences | Ignore whitespace | Details | Blame | Last modification | View Log | RSS feed
Rev 2106 | Rev 2131 | ||
---|---|---|---|
1 | /* |
1 | /* |
2 | * Copyright (c) 2005 Jakub Jermar |
2 | * Copyright (c) 2005 Jakub Jermar |
3 | * All rights reserved. |
3 | * All rights reserved. |
4 | * |
4 | * |
5 | * Redistribution and use in source and binary forms, with or without |
5 | * Redistribution and use in source and binary forms, with or without |
6 | * modification, are permitted provided that the following conditions |
6 | * modification, are permitted provided that the following conditions |
7 | * are met: |
7 | * are met: |
8 | * |
8 | * |
9 | * - Redistributions of source code must retain the above copyright |
9 | * - Redistributions of source code must retain the above copyright |
10 | * notice, this list of conditions and the following disclaimer. |
10 | * notice, this list of conditions and the following disclaimer. |
11 | * - Redistributions in binary form must reproduce the above copyright |
11 | * - Redistributions in binary form must reproduce the above copyright |
12 | * notice, this list of conditions and the following disclaimer in the |
12 | * notice, this list of conditions and the following disclaimer in the |
13 | * documentation and/or other materials provided with the distribution. |
13 | * documentation and/or other materials provided with the distribution. |
14 | * - The name of the author may not be used to endorse or promote products |
14 | * - The name of the author may not be used to endorse or promote products |
15 | * derived from this software without specific prior written permission. |
15 | * derived from this software without specific prior written permission. |
16 | * |
16 | * |
17 | * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR |
17 | * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR |
18 | * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES |
18 | * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES |
19 | * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. |
19 | * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. |
20 | * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, |
20 | * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, |
21 | * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT |
21 | * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT |
22 | * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, |
22 | * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, |
23 | * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY |
23 | * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY |
24 | * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT |
24 | * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT |
25 | * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF |
25 | * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF |
26 | * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. |
26 | * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. |
27 | */ |
27 | */ |
28 | 28 | ||
29 | /** @addtogroup genericmm |
29 | /** @addtogroup genericmm |
30 | * @{ |
30 | * @{ |
31 | */ |
31 | */ |
32 | /** @file |
32 | /** @file |
33 | */ |
33 | */ |
34 | 34 | ||
35 | #ifndef KERN_BUDDY_H_ |
35 | #ifndef KERN_BUDDY_H_ |
36 | #define KERN_BUDDY_H_ |
36 | #define KERN_BUDDY_H_ |
37 | 37 | ||
38 | #include <arch/types.h> |
38 | #include <arch/types.h> |
39 | #include <adt/list.h> |
39 | #include <adt/list.h> |
40 | 40 | ||
41 | #define BUDDY_SYSTEM_INNER_BLOCK 0xff |
41 | #define BUDDY_SYSTEM_INNER_BLOCK 0xff |
42 | 42 | ||
43 | struct buddy_system; |
43 | struct buddy_system; |
44 | 44 | ||
45 | /** Buddy system operations to be implemented by each implementation. */ |
45 | /** Buddy system operations to be implemented by each implementation. */ |
46 | typedef struct { |
46 | typedef struct { |
47 | /** |
47 | /** |
48 | * Return pointer to left-side or right-side buddy for block passed as |
48 | * Return pointer to left-side or right-side buddy for block passed as |
49 | * argument. |
49 | * argument. |
50 | */ |
50 | */ |
51 | link_t *(* find_buddy)(struct buddy_system *, link_t *); |
51 | link_t *(* find_buddy)(struct buddy_system *, link_t *); |
52 | /** |
52 | /** |
53 | * Bisect the block passed as argument and return pointer to the new |
53 | * Bisect the block passed as argument and return pointer to the new |
54 | * right-side buddy. |
54 | * right-side buddy. |
55 | */ |
55 | */ |
56 | link_t *(* bisect)(struct buddy_system *, link_t *); |
56 | link_t *(* bisect)(struct buddy_system *, link_t *); |
57 | /** Coalesce two buddies into a bigger block. */ |
57 | /** Coalesce two buddies into a bigger block. */ |
58 | link_t *(* coalesce)(struct buddy_system *, link_t *, link_t *); |
58 | link_t *(* coalesce)(struct buddy_system *, link_t *, link_t *); |
59 | /** Set order of block passed as argument. */ |
59 | /** Set order of block passed as argument. */ |
60 | void (*set_order)(struct buddy_system *, link_t *, uint8_t); |
60 | void (*set_order)(struct buddy_system *, link_t *, uint8_t); |
61 | /** Return order of block passed as argument. */ |
61 | /** Return order of block passed as argument. */ |
62 | uint8_t (*get_order)(struct buddy_system *, link_t *); |
62 | uint8_t (*get_order)(struct buddy_system *, link_t *); |
63 | /** Mark block as busy. */ |
63 | /** Mark block as busy. */ |
64 | void (*mark_busy)(struct buddy_system *, link_t *); |
64 | void (*mark_busy)(struct buddy_system *, link_t *); |
65 | /** Mark block as available. */ |
65 | /** Mark block as available. */ |
66 | void (*mark_available)(struct buddy_system *, link_t *); |
66 | void (*mark_available)(struct buddy_system *, link_t *); |
67 | /** Find parent of block that has given order */ |
67 | /** Find parent of block that has given order */ |
68 | link_t *(* find_block)(struct buddy_system *, link_t *, uint8_t); |
68 | link_t *(* find_block)(struct buddy_system *, link_t *, uint8_t); |
69 | void (* print_id)(struct buddy_system *, link_t *); |
69 | void (* print_id)(struct buddy_system *, link_t *); |
70 | } buddy_system_operations_t; |
70 | } buddy_system_operations_t; |
71 | 71 | ||
72 | typedef struct buddy_system { |
72 | typedef struct buddy_system { |
73 | /** Maximal order of block which can be stored by buddy system. */ |
73 | /** Maximal order of block which can be stored by buddy system. */ |
74 | uint8_t max_order; |
74 | uint8_t max_order; |
75 | link_t *order; |
75 | link_t *order; |
76 | buddy_system_operations_t *op; |
76 | buddy_system_operations_t *op; |
77 | /** Pointer to be used by the implementation. */ |
77 | /** Pointer to be used by the implementation. */ |
78 | void *data; |
78 | void *data; |
79 | } buddy_system_t; |
79 | } buddy_system_t; |
80 | 80 | ||
81 | extern void buddy_system_create(buddy_system_t *b, uint8_t max_order, |
81 | extern void buddy_system_create(buddy_system_t *b, uint8_t max_order, |
82 | buddy_system_operations_t *op, void *data); |
82 | buddy_system_operations_t *op, void *data); |
83 | extern link_t *buddy_system_alloc(buddy_system_t *b, uint8_t i); |
83 | extern link_t *buddy_system_alloc(buddy_system_t *b, uint8_t i); |
84 | extern bool buddy_system_can_alloc(buddy_system_t *b, uint8_t order); |
84 | extern bool buddy_system_can_alloc(buddy_system_t *b, uint8_t order); |
85 | extern void buddy_system_free(buddy_system_t *b, link_t *block); |
85 | extern void buddy_system_free(buddy_system_t *b, link_t *block); |
86 | extern void buddy_system_structure_print(buddy_system_t *b, size_t elem_size); |
86 | extern void buddy_system_structure_print(buddy_system_t *b, size_t elem_size); |
87 | extern size_t buddy_conf_size(int max_order); |
87 | extern size_t buddy_conf_size(int max_order); |
88 | extern link_t *buddy_system_alloc_block(buddy_system_t *b, link_t *block); |
88 | extern link_t *buddy_system_alloc_block(buddy_system_t *b, link_t *block); |
89 | 89 | ||
90 | #endif |
90 | #endif |
91 | 91 | ||
92 | /** @} |
92 | /** @} |
93 | */ |
93 | */ |
94 | 94 |