1 /*
2 * Copyright (c) 2015-2016 Los Alamos National Security, LLC. All
3 * rights reserved.
4 * Copyright (c) 2015-2016 Cray Inc. All rights reserved.
5 *
6 * This software is available to you under a choice of one of two
7 * licenses. You may choose to be licensed under the terms of the GNU
8 * General Public License (GPL) Version 2, available from the file
9 * COPYING in the main directory of this source tree, or the
10 * BSD license below:
11 *
12 * Redistribution and use in source and binary forms, with or
13 * without modification, are permitted provided that the following
14 * conditions are met:
15 *
16 * - Redistributions of source code must retain the above
17 * copyright notice, this list of conditions and the following
18 * disclaimer.
19 *
20 * - Redistributions in binary form must reproduce the above
21 * copyright notice, this list of conditions and the following
22 * disclaimer in the documentation and/or other materials
23 * provided with the distribution.
24 *
25 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
26 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
27 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
28 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS
29 * BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN
30 * ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
31 * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
32 * SOFTWARE.
33 */
34
35 #ifndef _GNIX_BUDDY_ALLOCATOR_H_
36 #define _GNIX_BUDDY_ALLOCATOR_H_
37
38 #include <stdlib.h>
39 #include "ofi_list.h"
40 #include "gnix_bitmap.h"
41 #include "gnix_util.h"
42 #include "gnix.h"
43
44 #define MIN_BLOCK_SIZE 256
45
46 /* The following table was taken from:
47 * http://graphics.stanford.edu/~seander/bithacks.html#IntegerLogDeBruijn
48 */
49 static const uint32_t MultiplyDeBruijnBitPosition[32] = {
50 0, 9, 1, 10, 13, 21, 2, 29, 11, 14, 16, 18, 22, 25, 3, 30,
51 8, 12, 20, 28, 15, 17, 24, 7, 19, 27, 23, 6, 26, 5, 4, 31
52 };
53
54 /* The following log2 function was taken from:
55 * http://graphics.stanford.edu/~seander/bithacks.html#IntegerLogDeBruijn.
56 *
57 * Note: this function always truncates the result.
58 */
__gnix_buddy_log2(uint32_t v)59 static inline uint32_t __gnix_buddy_log2(uint32_t v)
60 {
61 v |= v >> 1;
62 v |= v >> 2;
63 v |= v >> 4;
64 v |= v >> 8;
65 v |= v >> 16;
66
67 return MultiplyDeBruijnBitPosition[(uint32_t)(v * 0x07C4ACDDU) >> 27];
68 }
69
70 /* Find the bitmap index for block X of size X_LEN */
__gnix_buddy_bitmap_index(void * _x,size_t x_len,void * _base,size_t base_len,size_t min_len)71 static inline size_t __gnix_buddy_bitmap_index(void *_x, size_t x_len,
72 void *_base, size_t base_len,
73 size_t min_len)
74 {
75 /* arithmetic on void * is not part of the C standard (yet?) */
76 uint8_t *x = _x;
77 uint8_t *base = _base;
78
79 return (size_t) ((x - base) / (size_t) x_len) +
80 base_len / (min_len / 2) - base_len / (x_len / 2);
81 }
82
83 /* Find the address of X's buddy block:
84 * If the "index" of block X is even then the buddy must be to the right of X,
85 * otherwise the buddy is to the left of X.
86 */
__gnix_buddy_address(void * x,size_t len,void * base)87 static inline void *__gnix_buddy_address(void *x, size_t len, void *base)
88 {
89 return (void *) (((((size_t) base - (size_t) x) / len) % 2) ?
90 (size_t) x - len : (size_t) x + len);
91 }
92
93 /* evaluates to zero if X is not a power of two, otherwise evaluates to X - 1 */
94 #define IS_NOT_POW_TWO(X) (((X) & (~(X) + 1)) ^ (X))
95
96 /* Find the block size (in bytes) required for allocating LEN bytes */
97 #define BLOCK_SIZE(LEN, MIN_LEN) ((LEN) <= (MIN_LEN) ? (MIN_LEN) :\
98 (IS_NOT_POW_TWO(LEN)) ? (((LEN) << 1) & ~(LEN)) :\
99 (LEN))
100
101 /* Calculate the offset of a free block, OFFSET = MIN_LEN * 2^MULT. */
102 #define OFFSET(MIN_LEN, MULT) ((MIN_LEN) * (1 << (MULT)))
103
104 /* Find the index into the free list with block size LEN. */
105 #define LIST_INDEX(LEN, MIN_LEN) (__gnix_buddy_log2((LEN) / (MIN_LEN)))
106
107 /**
108 * Structure representing a buddy allocator.
109 *
110 * @var base The base address of the buffer being managed.
111 * @var len The length of the buffer the buddy allocator is
112 * managing.
113 * @var max The largest chunk of memory that can be allocated.
114 *
115 * @var nlists The number of free lists.
116 * @var lists The array of free lists ordered from smallest block
117 * size.
118 * at index 0 to largest block size at index nlists - 1.
119 *
120 * @var bitmap Each bit is 1 if the block is allocated or split,
121 * otherwise the bit is 0.
122 *
123 * @var lock The buddy alloc handle lock.
124 */
125 typedef struct gnix_buddy_alloc_handle {
126 void *base;
127 uint32_t len;
128 uint32_t max;
129
130 uint32_t nlists;
131 struct dlist_entry *lists;
132
133 gnix_bitmap_t bitmap;
134
135 fastlock_t lock;
136 } gnix_buddy_alloc_handle_t;
137
138 /**
139 * Creates a buddy allocator
140 *
141 * @param[in] base Base address of buffer to be managed by
142 * allocator.
143 *
144 * @param[in] len Size of the buffer to be managed by allocator
145 * (must be a multiple of max).
146 *
147 * @param[in] max Maximum amount of memory that can be allocated
148 * by a single call to _gnix_buddy_alloc (power 2).
149 *
150 * @param[in/out] alloc_handle Handle to be used for when allocating/freeing
151 * memory managed by the buddy allocator.
152 *
153 * @return FI_SUCCESS Upon successfully creating an allocator.
154 *
155 * @return -FI_EINVAL Upon an invalid parameter.
156 *
157 * @return -FI_ENOMEM Upon failure to allocate memory to create the
158 * buddy allocator.
159 */
160 int _gnix_buddy_allocator_create(void *base, uint32_t len, uint32_t max,
161 gnix_buddy_alloc_handle_t **alloc_handle);
162
163 /**
164 * Releases all resources associated with a buddy allocator handle.
165 *
166 * @param[in] alloc_handle Buddy alloc handle to destroy.
167 *
168 * @return FI_SUCCESS Upon successfully destroying an allocator.
169 *
170 * @return -FI_EINVAL Upon an invalid parameter.
171 */
172 int _gnix_buddy_allocator_destroy(gnix_buddy_alloc_handle_t *alloc_handle);
173
174 /**
175 * Allocate a buffer from the buddy allocator
176 *
177 * @param[in] alloc_handle Previously allocated GNI buddy_alloc_handle to
178 * use as allocator.
179 *
180 * @param[in/out] ptr Pointer to an address where the address of the
181 * allocated buffer will be returned.
182 *
183 * @param[in] len Size of buffer to allocate in bytes.
184 *
185 * @return FI_SUCCESS Upon successfully allocating a buffer.
186 *
187 * @return -FI_ENOMEM Upon not being able to allocate a buffer of the
188 * requested size.
189 *
190 * @return -FI_EINVAL Upon an invalid parameter.
191 */
192 int _gnix_buddy_alloc(gnix_buddy_alloc_handle_t *alloc_handle, void **ptr,
193 uint32_t len);
194
195 /**
196 * Free a previously allocated buffer
197 *
198 * @param[in] alloc_handle Previously allocated GNI buddy_alloc_handle to
199 * use as allocator.
200 *
201 * @param[in/out] ptr Pointer to the previously allocated block.
202 *
203 * @param[in] len Size of the previously allocated block.
204 *
205 * @return FI_SUCCESS Upon successfully freeing a block.
206 *
207 * @return -FI_EINVAL Upon an invalid parameter.
208 */
209 int _gnix_buddy_free(gnix_buddy_alloc_handle_t *alloc_handle, void *ptr,
210 uint32_t len);
211 #endif /* _GNIX_BUDDY_ALLOCATOR_H_ */
212