]>
Commit | Line | Data |
---|---|---|
ac5fb545 TB |
1 | /* |
2 | * Copyright (C) 2010 Tobias Brunner | |
e82186fb | 3 | * Copyright (C) 2008-2010 Martin Willi |
ac5fb545 TB |
4 | * Hochschule fuer Technik Rapperswil |
5 | * | |
6 | * This program is free software; you can redistribute it and/or modify it | |
7 | * under the terms of the GNU General Public License as published by the | |
8 | * Free Software Foundation; either version 2 of the License, or (at your | |
9 | * option) any later version. See <http://www.fsf.org/copyleft/gpl.txt>. | |
10 | * | |
11 | * This program is distributed in the hope that it will be useful, but | |
12 | * WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY | |
13 | * or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License | |
14 | * for more details. | |
15 | */ | |
16 | ||
17 | #include "mem_pool.h" | |
18 | ||
f05b4272 | 19 | #include <utils/debug.h> |
12642a68 TB |
20 | #include <collections/hashtable.h> |
21 | #include <collections/linked_list.h> | |
e82186fb | 22 | #include <threading/mutex.h> |
ac5fb545 TB |
23 | |
24 | #define POOL_LIMIT (sizeof(uintptr_t)*8) | |
25 | ||
26 | typedef struct private_mem_pool_t private_mem_pool_t; | |
27 | ||
28 | /** | |
29 | * private data of mem_pool_t | |
30 | */ | |
31 | struct private_mem_pool_t { | |
32 | /** | |
33 | * public interface | |
34 | */ | |
35 | mem_pool_t public; | |
36 | ||
37 | /** | |
38 | * name of the pool | |
39 | */ | |
40 | char *name; | |
41 | ||
42 | /** | |
43 | * base address of the pool | |
44 | */ | |
45 | host_t *base; | |
46 | ||
47 | /** | |
48 | * size of the pool | |
49 | */ | |
50 | u_int size; | |
51 | ||
52 | /** | |
53 | * next unused address | |
54 | */ | |
55 | u_int unused; | |
56 | ||
57 | /** | |
e82186fb | 58 | * lease hashtable [identity => entry] |
ac5fb545 | 59 | */ |
e82186fb | 60 | hashtable_t *leases; |
fb111e55 TB |
61 | |
62 | /** | |
63 | * lock to safely access the pool | |
64 | */ | |
e82186fb | 65 | mutex_t *mutex; |
ac5fb545 TB |
66 | }; |
67 | ||
e82186fb MW |
68 | /** |
69 | * Lease entry. | |
70 | */ | |
71 | typedef struct { | |
72 | /* identitiy reference */ | |
73 | identification_t *id; | |
74 | /* list of online leases, as offset */ | |
75 | linked_list_t *online; | |
76 | /* list of offline leases, as offset */ | |
77 | linked_list_t *offline; | |
78 | } entry_t; | |
79 | ||
ac5fb545 TB |
80 | /** |
81 | * hashtable hash function for identities | |
82 | */ | |
83 | static u_int id_hash(identification_t *id) | |
84 | { | |
85 | return chunk_hash(id->get_encoding(id)); | |
86 | } | |
87 | ||
88 | /** | |
89 | * hashtable equals function for identities | |
90 | */ | |
91 | static bool id_equals(identification_t *a, identification_t *b) | |
92 | { | |
93 | return a->equals(a, b); | |
94 | } | |
95 | ||
96 | /** | |
97 | * convert a pool offset to an address | |
98 | */ | |
99 | static host_t* offset2host(private_mem_pool_t *pool, int offset) | |
100 | { | |
101 | chunk_t addr; | |
102 | host_t *host; | |
103 | u_int32_t *pos; | |
104 | ||
105 | offset--; | |
106 | if (offset > pool->size) | |
107 | { | |
108 | return NULL; | |
109 | } | |
110 | ||
111 | addr = chunk_clone(pool->base->get_address(pool->base)); | |
112 | if (pool->base->get_family(pool->base) == AF_INET6) | |
113 | { | |
114 | pos = (u_int32_t*)(addr.ptr + 12); | |
115 | } | |
116 | else | |
117 | { | |
118 | pos = (u_int32_t*)addr.ptr; | |
119 | } | |
120 | *pos = htonl(offset + ntohl(*pos)); | |
121 | host = host_create_from_chunk(pool->base->get_family(pool->base), addr, 0); | |
122 | free(addr.ptr); | |
123 | return host; | |
124 | } | |
125 | ||
126 | /** | |
127 | * convert a host to a pool offset | |
128 | */ | |
129 | static int host2offset(private_mem_pool_t *pool, host_t *addr) | |
130 | { | |
131 | chunk_t host, base; | |
132 | u_int32_t hosti, basei; | |
133 | ||
134 | if (addr->get_family(addr) != pool->base->get_family(pool->base)) | |
135 | { | |
136 | return -1; | |
137 | } | |
138 | host = addr->get_address(addr); | |
139 | base = pool->base->get_address(pool->base); | |
140 | if (addr->get_family(addr) == AF_INET6) | |
141 | { | |
142 | /* only look at last /32 block */ | |
143 | if (!memeq(host.ptr, base.ptr, 12)) | |
144 | { | |
145 | return -1; | |
146 | } | |
147 | host = chunk_skip(host, 12); | |
148 | base = chunk_skip(base, 12); | |
149 | } | |
150 | hosti = ntohl(*(u_int32_t*)(host.ptr)); | |
151 | basei = ntohl(*(u_int32_t*)(base.ptr)); | |
152 | if (hosti > basei + pool->size) | |
153 | { | |
154 | return -1; | |
155 | } | |
156 | return hosti - basei + 1; | |
157 | } | |
158 | ||
159 | METHOD(mem_pool_t, get_name, const char*, | |
e82186fb | 160 | private_mem_pool_t *this) |
ac5fb545 TB |
161 | { |
162 | return this->name; | |
163 | } | |
164 | ||
d8eec395 MW |
165 | METHOD(mem_pool_t, get_base, host_t*, |
166 | private_mem_pool_t *this) | |
167 | { | |
168 | return this->base; | |
169 | } | |
170 | ||
ac5fb545 | 171 | METHOD(mem_pool_t, get_size, u_int, |
e82186fb | 172 | private_mem_pool_t *this) |
ac5fb545 TB |
173 | { |
174 | return this->size; | |
175 | } | |
176 | ||
177 | METHOD(mem_pool_t, get_online, u_int, | |
e82186fb | 178 | private_mem_pool_t *this) |
ac5fb545 | 179 | { |
e82186fb MW |
180 | enumerator_t *enumerator; |
181 | entry_t *entry; | |
182 | u_int count = 0; | |
183 | ||
184 | this->mutex->lock(this->mutex); | |
185 | enumerator = this->leases->create_enumerator(this->leases); | |
186 | while (enumerator->enumerate(enumerator, NULL, &entry)) | |
187 | { | |
188 | count += entry->online->get_count(entry->online); | |
189 | } | |
190 | enumerator->destroy(enumerator); | |
191 | this->mutex->unlock(this->mutex); | |
192 | ||
fb111e55 | 193 | return count; |
ac5fb545 TB |
194 | } |
195 | ||
196 | METHOD(mem_pool_t, get_offline, u_int, | |
e82186fb | 197 | private_mem_pool_t *this) |
ac5fb545 | 198 | { |
e82186fb MW |
199 | enumerator_t *enumerator; |
200 | entry_t *entry; | |
201 | u_int count = 0; | |
202 | ||
203 | this->mutex->lock(this->mutex); | |
204 | enumerator = this->leases->create_enumerator(this->leases); | |
205 | while (enumerator->enumerate(enumerator, NULL, &entry)) | |
206 | { | |
207 | count += entry->offline->get_count(entry->offline); | |
208 | } | |
209 | enumerator->destroy(enumerator); | |
210 | this->mutex->unlock(this->mutex); | |
211 | ||
fb111e55 | 212 | return count; |
ac5fb545 TB |
213 | } |
214 | ||
1e04488f MW |
215 | /** |
216 | * Get an existing lease for id | |
217 | */ | |
218 | static int get_existing(private_mem_pool_t *this, identification_t *id, | |
219 | host_t *requested) | |
ac5fb545 | 220 | { |
ac5fb545 | 221 | enumerator_t *enumerator; |
1e04488f MW |
222 | uintptr_t current; |
223 | entry_t *entry; | |
224 | int offset = 0; | |
225 | ||
226 | entry = this->leases->get(this->leases, id); | |
227 | if (!entry) | |
228 | { | |
229 | return 0; | |
230 | } | |
231 | ||
232 | /* check for a valid offline lease, refresh */ | |
233 | enumerator = entry->offline->create_enumerator(entry->offline); | |
234 | if (enumerator->enumerate(enumerator, ¤t)) | |
235 | { | |
236 | entry->offline->remove_at(entry->offline, enumerator); | |
237 | entry->online->insert_last(entry->online, (void*)current); | |
238 | offset = current; | |
239 | } | |
240 | enumerator->destroy(enumerator); | |
241 | if (offset) | |
242 | { | |
243 | DBG1(DBG_CFG, "reassigning offline lease to '%Y'", id); | |
244 | return offset; | |
245 | } | |
246 | ||
247 | /* check for a valid online lease to reassign */ | |
248 | enumerator = entry->online->create_enumerator(entry->online); | |
249 | while (enumerator->enumerate(enumerator, ¤t)) | |
250 | { | |
251 | if (current == host2offset(this, requested)) | |
252 | { | |
253 | offset = current; | |
254 | break; | |
255 | } | |
256 | } | |
257 | enumerator->destroy(enumerator); | |
258 | if (offset) | |
259 | { | |
260 | DBG1(DBG_CFG, "reassigning online lease to '%Y'", id); | |
261 | } | |
262 | return offset; | |
263 | } | |
264 | ||
265 | /** | |
266 | * Get a new lease for id | |
267 | */ | |
268 | static int get_new(private_mem_pool_t *this, identification_t *id) | |
269 | { | |
270 | entry_t *entry; | |
5b96503e | 271 | uintptr_t offset = 0; |
1e04488f MW |
272 | |
273 | if (this->unused < this->size) | |
274 | { | |
f0a2fef8 MW |
275 | entry = this->leases->get(this->leases, id); |
276 | if (!entry) | |
277 | { | |
278 | INIT(entry, | |
279 | .id = id->clone(id), | |
280 | .online = linked_list_create(), | |
281 | .offline = linked_list_create(), | |
282 | ); | |
283 | this->leases->put(this->leases, entry->id, entry); | |
284 | } | |
1e04488f MW |
285 | /* assigning offset, starting by 1 */ |
286 | offset = ++this->unused; | |
287 | entry->online->insert_last(entry->online, (void*)offset); | |
288 | DBG1(DBG_CFG, "assigning new lease to '%Y'", id); | |
289 | } | |
290 | return offset; | |
291 | } | |
292 | ||
293 | /** | |
294 | * Get a reassigned lease for id in case the pool is full | |
295 | */ | |
296 | static int get_reassigned(private_mem_pool_t *this, identification_t *id) | |
297 | { | |
298 | enumerator_t *enumerator; | |
299 | entry_t *entry; | |
5b96503e | 300 | uintptr_t current, offset = 0; |
1e04488f MW |
301 | |
302 | enumerator = this->leases->create_enumerator(this->leases); | |
303 | while (enumerator->enumerate(enumerator, NULL, &entry)) | |
304 | { | |
305 | if (entry->offline->remove_first(entry->offline, | |
306 | (void**)¤t) == SUCCESS) | |
307 | { | |
308 | offset = current; | |
309 | DBG1(DBG_CFG, "reassigning existing offline lease by '%Y'" | |
310 | " to '%Y'", entry->id, id); | |
311 | break; | |
312 | } | |
313 | } | |
314 | enumerator->destroy(enumerator); | |
315 | ||
316 | if (offset) | |
317 | { | |
318 | INIT(entry, | |
319 | .id = id->clone(id), | |
320 | .online = linked_list_create(), | |
321 | .offline = linked_list_create(), | |
322 | ); | |
323 | entry->online->insert_last(entry->online, (void*)offset); | |
324 | this->leases->put(this->leases, entry->id, entry); | |
325 | } | |
326 | return offset; | |
327 | } | |
328 | ||
329 | METHOD(mem_pool_t, acquire_address, host_t*, | |
330 | private_mem_pool_t *this, identification_t *id, host_t *requested, | |
331 | mem_pool_op_t operation) | |
332 | { | |
333 | int offset = 0; | |
ac5fb545 TB |
334 | |
335 | /* if the pool is empty (e.g. in the %config case) we simply return the | |
336 | * requested address */ | |
337 | if (this->size == 0) | |
338 | { | |
339 | return requested->clone(requested); | |
340 | } | |
341 | ||
40e90898 | 342 | if (requested->get_family(requested) != |
fb111e55 | 343 | this->base->get_family(this->base)) |
ac5fb545 | 344 | { |
fb111e55 TB |
345 | return NULL; |
346 | } | |
ac5fb545 | 347 | |
e82186fb | 348 | this->mutex->lock(this->mutex); |
1e04488f | 349 | switch (operation) |
fb111e55 | 350 | { |
1e04488f MW |
351 | case MEM_POOL_EXISTING: |
352 | offset = get_existing(this, id, requested); | |
ac5fb545 | 353 | break; |
1e04488f MW |
354 | case MEM_POOL_NEW: |
355 | offset = get_new(this, id); | |
356 | break; | |
357 | case MEM_POOL_REASSIGN: | |
358 | offset = get_reassigned(this, id); | |
359 | if (!offset) | |
ac5fb545 | 360 | { |
1e04488f MW |
361 | DBG1(DBG_CFG, "pool '%s' is full, unable to assign address", |
362 | this->name); | |
ac5fb545 | 363 | } |
1e04488f MW |
364 | break; |
365 | default: | |
366 | break; | |
ac5fb545 | 367 | } |
e82186fb | 368 | this->mutex->unlock(this->mutex); |
ac5fb545 TB |
369 | |
370 | if (offset) | |
371 | { | |
372 | return offset2host(this, offset); | |
373 | } | |
374 | return NULL; | |
375 | } | |
376 | ||
377 | METHOD(mem_pool_t, release_address, bool, | |
e82186fb | 378 | private_mem_pool_t *this, host_t *address, identification_t *id) |
ac5fb545 | 379 | { |
fb111e55 | 380 | bool found = FALSE; |
e82186fb MW |
381 | entry_t *entry; |
382 | uintptr_t offset; | |
383 | ||
ac5fb545 TB |
384 | if (this->size != 0) |
385 | { | |
e82186fb MW |
386 | this->mutex->lock(this->mutex); |
387 | entry = this->leases->get(this->leases, id); | |
388 | if (entry) | |
ac5fb545 | 389 | { |
e82186fb MW |
390 | offset = host2offset(this, address); |
391 | if (entry->online->remove(entry->online, (void*)offset, NULL) > 0) | |
ac5fb545 | 392 | { |
894936ce | 393 | DBG1(DBG_CFG, "lease %H by '%Y' went offline", address, id); |
e82186fb | 394 | entry->offline->insert_last(entry->offline, (void*)offset); |
fb111e55 | 395 | found = TRUE; |
ac5fb545 TB |
396 | } |
397 | } | |
e82186fb | 398 | this->mutex->unlock(this->mutex); |
ac5fb545 | 399 | } |
fb111e55 | 400 | return found; |
ac5fb545 TB |
401 | } |
402 | ||
403 | /** | |
404 | * lease enumerator | |
405 | */ | |
406 | typedef struct { | |
407 | /** implemented enumerator interface */ | |
408 | enumerator_t public; | |
e82186fb MW |
409 | /** hash-table enumerator */ |
410 | enumerator_t *entries; | |
411 | /** online enumerator */ | |
412 | enumerator_t *online; | |
413 | /** offline enumerator */ | |
414 | enumerator_t *offline; | |
ac5fb545 TB |
415 | /** enumerated pool */ |
416 | private_mem_pool_t *pool; | |
e82186fb MW |
417 | /** currently enumerated entry */ |
418 | entry_t *entry; | |
ac5fb545 | 419 | /** currently enumerated lease address */ |
e82186fb | 420 | host_t *addr; |
ac5fb545 TB |
421 | } lease_enumerator_t; |
422 | ||
423 | METHOD(enumerator_t, lease_enumerate, bool, | |
e82186fb | 424 | lease_enumerator_t *this, identification_t **id, host_t **addr, bool *online) |
ac5fb545 | 425 | { |
ac5fb545 TB |
426 | uintptr_t offset; |
427 | ||
e82186fb MW |
428 | DESTROY_IF(this->addr); |
429 | this->addr = NULL; | |
ac5fb545 | 430 | |
e82186fb | 431 | while (TRUE) |
ac5fb545 | 432 | { |
e82186fb | 433 | if (this->entry) |
ac5fb545 | 434 | { |
e82186fb MW |
435 | if (this->online->enumerate(this->online, (void**)&offset)) |
436 | { | |
437 | *id = this->entry->id; | |
438 | *addr = this->addr = offset2host(this->pool, offset); | |
439 | *online = TRUE; | |
440 | return TRUE; | |
441 | } | |
442 | if (this->offline->enumerate(this->offline, (void**)&offset)) | |
443 | { | |
444 | *id = this->entry->id; | |
445 | *addr = this->addr = offset2host(this->pool, offset); | |
446 | *online = FALSE; | |
447 | return TRUE; | |
448 | } | |
449 | this->online->destroy(this->online); | |
450 | this->offline->destroy(this->offline); | |
451 | this->online = this->offline = NULL; | |
ac5fb545 | 452 | } |
e82186fb | 453 | if (!this->entries->enumerate(this->entries, NULL, &this->entry)) |
ac5fb545 | 454 | { |
e82186fb | 455 | return FALSE; |
ac5fb545 | 456 | } |
e82186fb MW |
457 | this->online = this->entry->online->create_enumerator( |
458 | this->entry->online); | |
459 | this->offline = this->entry->offline->create_enumerator( | |
460 | this->entry->offline); | |
ac5fb545 | 461 | } |
ac5fb545 TB |
462 | } |
463 | ||
464 | METHOD(enumerator_t, lease_enumerator_destroy, void, | |
e82186fb | 465 | lease_enumerator_t *this) |
ac5fb545 | 466 | { |
e82186fb MW |
467 | DESTROY_IF(this->addr); |
468 | DESTROY_IF(this->online); | |
469 | DESTROY_IF(this->offline); | |
470 | this->entries->destroy(this->entries); | |
471 | this->pool->mutex->unlock(this->pool->mutex); | |
ac5fb545 TB |
472 | free(this); |
473 | } | |
474 | ||
475 | METHOD(mem_pool_t, create_lease_enumerator, enumerator_t*, | |
476 | private_mem_pool_t *this) | |
477 | { | |
478 | lease_enumerator_t *enumerator; | |
e82186fb MW |
479 | |
480 | this->mutex->lock(this->mutex); | |
ac5fb545 TB |
481 | INIT(enumerator, |
482 | .public = { | |
483 | .enumerate = (void*)_lease_enumerate, | |
e82186fb | 484 | .destroy = _lease_enumerator_destroy, |
ac5fb545 TB |
485 | }, |
486 | .pool = this, | |
e82186fb | 487 | .entries = this->leases->create_enumerator(this->leases), |
ac5fb545 | 488 | ); |
ac5fb545 TB |
489 | return &enumerator->public; |
490 | } | |
491 | ||
492 | METHOD(mem_pool_t, destroy, void, | |
e82186fb | 493 | private_mem_pool_t *this) |
ac5fb545 TB |
494 | { |
495 | enumerator_t *enumerator; | |
e82186fb | 496 | entry_t *entry; |
ac5fb545 | 497 | |
e82186fb MW |
498 | enumerator = this->leases->create_enumerator(this->leases); |
499 | while (enumerator->enumerate(enumerator, NULL, &entry)) | |
ac5fb545 | 500 | { |
e82186fb MW |
501 | entry->id->destroy(entry->id); |
502 | entry->online->destroy(entry->online); | |
503 | entry->offline->destroy(entry->offline); | |
504 | free(entry); | |
ac5fb545 TB |
505 | } |
506 | enumerator->destroy(enumerator); | |
507 | ||
e82186fb MW |
508 | this->leases->destroy(this->leases); |
509 | this->mutex->destroy(this->mutex); | |
ac5fb545 TB |
510 | DESTROY_IF(this->base); |
511 | free(this->name); | |
512 | free(this); | |
513 | } | |
514 | ||
515 | /** | |
516 | * Described in header | |
517 | */ | |
518 | mem_pool_t *mem_pool_create(char *name, host_t *base, int bits) | |
519 | { | |
520 | private_mem_pool_t *this; | |
e82186fb | 521 | int addr_bits; |
ac5fb545 TB |
522 | |
523 | INIT(this, | |
524 | .public = { | |
525 | .get_name = _get_name, | |
d8eec395 | 526 | .get_base = _get_base, |
ac5fb545 TB |
527 | .get_size = _get_size, |
528 | .get_online = _get_online, | |
529 | .get_offline = _get_offline, | |
530 | .acquire_address = _acquire_address, | |
531 | .release_address = _release_address, | |
532 | .create_lease_enumerator = _create_lease_enumerator, | |
533 | .destroy = _destroy, | |
534 | }, | |
535 | .name = strdup(name), | |
e82186fb | 536 | .leases = hashtable_create((hashtable_hash_t)id_hash, |
ac5fb545 | 537 | (hashtable_equals_t)id_equals, 16), |
e82186fb | 538 | .mutex = mutex_create(MUTEX_TYPE_DEFAULT), |
ac5fb545 TB |
539 | ); |
540 | ||
541 | if (base) | |
542 | { | |
e82186fb | 543 | addr_bits = base->get_family(base) == AF_INET ? 32 : 128; |
3a917ac7 | 544 | bits = max(0, min(bits, base->get_family(base) == AF_INET ? 32 : 128)); |
ac5fb545 TB |
545 | /* net bits -> host bits */ |
546 | bits = addr_bits - bits; | |
547 | if (bits > POOL_LIMIT) | |
548 | { | |
549 | bits = POOL_LIMIT; | |
894936ce | 550 | DBG1(DBG_CFG, "virtual IP pool too large, limiting to %H/%d", |
ac5fb545 TB |
551 | base, addr_bits - bits); |
552 | } | |
553 | this->size = 1 << (bits); | |
554 | ||
555 | if (this->size > 2) | |
556 | { /* do not use first and last addresses of a block */ | |
557 | this->unused++; | |
747fd544 | 558 | this->size -= 2; |
ac5fb545 TB |
559 | } |
560 | this->base = base->clone(base); | |
561 | } | |
562 | ||
563 | return &this->public; | |
564 | } | |
565 |