]>
Commit | Line | Data |
---|---|---|
2bc8fa02 RB |
1 | #include "pool.h" |
2 | #ifndef GIT_WIN32 | |
3 | #include <unistd.h> | |
4 | #endif | |
5 | ||
6 | struct git_pool_page { | |
7 | git_pool_page *next; | |
8 | uint32_t size; | |
9 | uint32_t avail; | |
10 | char data[GIT_FLEX_ARRAY]; | |
11 | }; | |
12 | ||
13 | #define GIT_POOL_MIN_USABLE 4 | |
14 | #define GIT_POOL_MIN_PAGESZ 2 * sizeof(void*) | |
15 | ||
16 | static int pool_alloc_page(git_pool *pool, uint32_t size, void **ptr); | |
17 | static void pool_insert_page(git_pool *pool, git_pool_page *page); | |
18 | ||
19 | int git_pool_init( | |
20 | git_pool *pool, uint32_t item_size, uint32_t items_per_page) | |
21 | { | |
22 | assert(pool); | |
23 | ||
24 | if (!item_size) | |
25 | item_size = 1; | |
26 | /* round up item_size for decent object alignment */ | |
27 | if (item_size > 4) | |
28 | item_size = (item_size + 7) & ~7; | |
29 | else if (item_size == 3) | |
30 | item_size = 4; | |
31 | ||
32 | if (!items_per_page) { | |
33 | uint32_t page_bytes = | |
34 | git_pool__system_page_size() - sizeof(git_pool_page); | |
35 | items_per_page = page_bytes / item_size; | |
36 | } | |
37 | if (item_size * items_per_page < GIT_POOL_MIN_PAGESZ) | |
38 | items_per_page = (GIT_POOL_MIN_PAGESZ + item_size - 1) / item_size; | |
39 | ||
40 | memset(pool, 0, sizeof(git_pool)); | |
41 | pool->item_size = item_size; | |
42 | pool->page_size = item_size * items_per_page; | |
43 | ||
44 | return 0; | |
45 | } | |
46 | ||
47 | void git_pool_clear(git_pool *pool) | |
48 | { | |
49 | git_pool_page *scan, *next; | |
50 | ||
51 | for (scan = pool->open; scan != NULL; scan = next) { | |
52 | next = scan->next; | |
53 | git__free(scan); | |
54 | } | |
55 | pool->open = NULL; | |
56 | ||
57 | for (scan = pool->full; scan != NULL; scan = next) { | |
58 | next = scan->next; | |
59 | git__free(scan); | |
60 | } | |
61 | pool->full = NULL; | |
62 | ||
63 | pool->free_list = NULL; | |
64 | ||
65 | pool->has_string_alloc = 0; | |
66 | pool->has_multi_item_alloc = 0; | |
67 | pool->has_large_page_alloc = 0; | |
68 | } | |
69 | ||
70 | static void pool_insert_page(git_pool *pool, git_pool_page *page) | |
71 | { | |
72 | git_pool_page *scan; | |
73 | ||
74 | /* If there are no open pages or this page has the most open space, | |
75 | * insert it at the beginning of the list. This is the common case. | |
76 | */ | |
77 | if (pool->open == NULL || pool->open->avail < page->avail) { | |
78 | page->next = pool->open; | |
79 | pool->open = page; | |
80 | return; | |
81 | } | |
82 | ||
83 | /* Otherwise insert into sorted position. */ | |
84 | for (scan = pool->open; | |
85 | scan->next && scan->next->avail > page->avail; | |
86 | scan = scan->next); | |
87 | page->next = scan->next; | |
88 | scan->next = page; | |
89 | } | |
90 | ||
91 | static int pool_alloc_page( | |
92 | git_pool *pool, uint32_t size, void **ptr) | |
93 | { | |
94 | git_pool_page *page; | |
95 | uint32_t alloc_size; | |
96 | ||
97 | if (size <= pool->page_size) | |
98 | alloc_size = pool->page_size; | |
99 | else { | |
100 | alloc_size = size; | |
101 | pool->has_large_page_alloc = 1; | |
102 | } | |
103 | ||
104 | page = git__calloc(1, alloc_size + sizeof(git_pool_page)); | |
105 | if (!page) | |
106 | return -1; | |
107 | ||
108 | page->size = alloc_size; | |
109 | page->avail = alloc_size - size; | |
110 | ||
111 | if (page->avail > 0) | |
112 | pool_insert_page(pool, page); | |
113 | else { | |
114 | page->next = pool->full; | |
115 | pool->full = page; | |
116 | } | |
117 | ||
118 | *ptr = page->data; | |
119 | ||
120 | return 0; | |
121 | } | |
122 | ||
123 | GIT_INLINE(void) pool_remove_page( | |
124 | git_pool *pool, git_pool_page *page, git_pool_page *prev) | |
125 | { | |
126 | if (prev == NULL) | |
127 | pool->open = page->next; | |
128 | else | |
129 | prev->next = page->next; | |
130 | } | |
131 | ||
132 | int git_pool_malloc(git_pool *pool, uint32_t items, void **ptr) | |
133 | { | |
134 | git_pool_page *scan = pool->open, *prev; | |
135 | uint32_t size = items * pool->item_size; | |
136 | ||
137 | pool->has_string_alloc = 0; | |
138 | if (items > 1) | |
139 | pool->has_multi_item_alloc = 1; | |
140 | else if (pool->free_list != NULL) { | |
141 | *ptr = pool->free_list; | |
142 | pool->free_list = *((void **)pool->free_list); | |
143 | } | |
144 | ||
145 | /* just add a block if there is no open one to accomodate this */ | |
146 | if (size >= pool->page_size || !scan || scan->avail < size) | |
147 | return pool_alloc_page(pool, size, ptr); | |
148 | ||
149 | /* find smallest block in free list with space */ | |
150 | for (scan = pool->open, prev = NULL; | |
151 | scan->next && scan->next->avail >= size; | |
152 | prev = scan, scan = scan->next); | |
153 | ||
154 | /* allocate space from the block */ | |
155 | *ptr = &scan->data[scan->size - scan->avail]; | |
156 | scan->avail -= size; | |
157 | ||
158 | /* move to full list if there is almost no space left */ | |
159 | if (scan->avail < pool->item_size || scan->avail < GIT_POOL_MIN_USABLE) { | |
160 | pool_remove_page(pool, scan, prev); | |
161 | scan->next = pool->full; | |
162 | pool->full = scan; | |
163 | } | |
164 | /* reorder list if block is now smaller than the one after it */ | |
165 | else if (scan->next != NULL && scan->next->avail > scan->avail) { | |
166 | pool_remove_page(pool, scan, prev); | |
167 | pool_insert_page(pool, scan); | |
168 | } | |
169 | ||
170 | return 0; | |
171 | } | |
172 | ||
173 | char *git_pool_strndup(git_pool *pool, const char *str, size_t n) | |
174 | { | |
175 | void *ptr = NULL; | |
176 | ||
177 | assert(pool && str && pool->item_size == sizeof(char)); | |
178 | ||
179 | if (!git_pool_malloc(pool, n, &ptr)) | |
180 | memcpy(ptr, str, n); | |
181 | pool->has_string_alloc = 1; | |
182 | ||
183 | return ptr; | |
184 | } | |
185 | ||
186 | char *git_pool_strdup(git_pool *pool, const char *str) | |
187 | { | |
188 | assert(pool && str && pool->item_size == sizeof(char)); | |
189 | ||
190 | return git_pool_strndup(pool, str, strlen(str) + 1); | |
191 | } | |
192 | ||
193 | void git_pool_free(git_pool *pool, void *ptr) | |
194 | { | |
195 | assert(pool && ptr && pool->item_size >= sizeof(void*)); | |
196 | ||
197 | *((void **)ptr) = pool->free_list; | |
198 | pool->free_list = ptr; | |
199 | } | |
200 | ||
201 | uint32_t git_pool__open_pages(git_pool *pool) | |
202 | { | |
203 | uint32_t ct = 0; | |
204 | git_pool_page *scan; | |
205 | for (scan = pool->open; scan != NULL; scan = scan->next) ct++; | |
206 | return ct; | |
207 | } | |
208 | ||
209 | uint32_t git_pool__full_pages(git_pool *pool) | |
210 | { | |
211 | uint32_t ct = 0; | |
212 | git_pool_page *scan; | |
213 | for (scan = pool->full; scan != NULL; scan = scan->next) ct++; | |
214 | return ct; | |
215 | } | |
216 | ||
217 | bool git_pool__ptr_in_pool(git_pool *pool, void *ptr) | |
218 | { | |
219 | git_pool_page *scan; | |
220 | for (scan = pool->open; scan != NULL; scan = scan->next) | |
221 | if ( ((void *)scan->data) <= ptr && | |
222 | (((void *)scan->data) + scan->size) > ptr) | |
223 | return true; | |
224 | for (scan = pool->full; scan != NULL; scan = scan->next) | |
225 | if ( ((void *)scan->data) <= ptr && | |
226 | (((void *)scan->data) + scan->size) > ptr) | |
227 | return true; | |
228 | return false; | |
229 | } | |
230 | ||
231 | uint32_t git_pool__system_page_size(void) | |
232 | { | |
233 | static uint32_t size = 0; | |
234 | ||
235 | if (!size) { | |
236 | #ifdef GIT_WIN32 | |
237 | SYSTEM_INFO info; | |
238 | GetSystemInfo(&info); | |
239 | size = (uint32_t)info.dwPageSize; | |
240 | #else | |
241 | size = (uint32_t)sysconf(_SC_PAGE_SIZE); | |
242 | #endif | |
243 | ||
244 | size -= 2 * sizeof(void *); /* allow space for malloc overhead */ | |
245 | } | |
246 | ||
247 | return size; | |
248 | } | |
249 |