1 /*
2 * Copyright (c) 2002-2012 Balabit
3 * Copyright (c) 1998-2012 Balázs Scheidler
4 *
5 * This library is free software; you can redistribute it and/or
6 * modify it under the terms of the GNU Lesser General Public
7 * License as published by the Free Software Foundation; either
8 * version 2.1 of the License, or (at your option) any later version.
9 *
10 * This library is distributed in the hope that it will be useful,
11 * but WITHOUT ANY WARRANTY; without even the implied warranty of
12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
13 * Lesser General Public License for more details.
14 *
15 * You should have received a copy of the GNU Lesser General Public
16 * License along with this library; if not, write to the Free Software
17 * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
18 *
19 * As an additional exemption you are allowed to compile & link against the
20 * OpenSSL libraries as published by the OpenSSL project. See the file
21 * COPYING for details.
22 *
23 */
24 #include "logmsg/nvtable.h"
25 #include "messages.h"
26
27 #include <string.h>
28 #include <stdlib.h>
29
30 static GMutex nv_registry_lock;
31
32 const gchar *null_string = "";
33
34 NVHandle
nv_registry_get_handle(NVRegistry * self,const gchar * name)35 nv_registry_get_handle(NVRegistry *self, const gchar *name)
36 {
37 gpointer p;
38
39 p = g_hash_table_lookup(self->name_map, name);
40 if (p)
41 return GPOINTER_TO_UINT(p);
42 return 0;
43 }
44
45 NVHandle
nv_registry_alloc_handle(NVRegistry * self,const gchar * name)46 nv_registry_alloc_handle(NVRegistry *self, const gchar *name)
47 {
48 gpointer p;
49 NVHandleDesc stored;
50 gsize len;
51 NVHandle res = 0;
52
53 g_mutex_lock(&nv_registry_lock);
54 p = g_hash_table_lookup(self->name_map, name);
55 if (p)
56 {
57 res = GPOINTER_TO_UINT(p);
58 goto exit;
59 }
60
61 len = strlen(name);
62 if (len == 0)
63 goto exit;
64
65 if (len > 255)
66 {
67 msg_error("Value names cannot be longer than 255 characters, "
68 "this value will always expand to the empty string",
69 evt_tag_str("value", name));
70 goto exit;
71 }
72
73 if (self->names->len >= self->nvhandle_max_value)
74 {
75 msg_error("Hard wired limit of name-value pairs have been reached, "
76 "all further name-value pair will expand to nothing",
77 evt_tag_printf("limit", "%"G_GUINT32_FORMAT, self->nvhandle_max_value),
78 evt_tag_str("value", name));
79 goto exit;
80 }
81
82 /* name (len bytes) || NULL || flags (2 bytes) || length (1 byte) */
83 /* memory layout: name (NUL terminated) || flags || length */
84 stored.flags = 0;
85 stored.name_len = len;
86 stored.name = g_strdup(name);
87 nvhandle_desc_array_append(self->names, &stored);
88 g_hash_table_insert(self->name_map, g_strdup(name), GUINT_TO_POINTER(self->names->len));
89 res = self->names->len;
90 exit:
91 g_mutex_unlock(&nv_registry_lock);
92 return res;
93 }
94
95 /**
96 * nv_registry_add_alias:
97 * @handle: a NV handle to be aliased
98 * @alias: must be a caller allocated string pointing to the alias of "handle"
99 **/
100 void
nv_registry_add_alias(NVRegistry * self,NVHandle handle,const gchar * alias)101 nv_registry_add_alias(NVRegistry *self, NVHandle handle, const gchar *alias)
102 {
103 g_mutex_lock(&nv_registry_lock);
104 g_hash_table_insert(self->name_map, g_strdup(alias), GUINT_TO_POINTER((glong) handle));
105 g_mutex_unlock(&nv_registry_lock);
106 }
107
108 void
nv_registry_set_handle_flags(NVRegistry * self,NVHandle handle,guint16 flags)109 nv_registry_set_handle_flags(NVRegistry *self, NVHandle handle, guint16 flags)
110 {
111 NVHandleDesc *stored;
112
113 if (G_UNLIKELY(!handle))
114 return;
115
116 stored = &nvhandle_desc_array_index(self->names, handle - 1);
117 stored->flags = flags;
118 }
119
120 void
nv_registry_foreach(NVRegistry * self,GHFunc callback,gpointer user_data)121 nv_registry_foreach(NVRegistry *self, GHFunc callback, gpointer user_data)
122 {
123 g_hash_table_foreach(self->name_map, callback, user_data);
124 }
125
126 NVRegistry *
nv_registry_new(const gchar ** static_names,guint32 nvhandle_max_value)127 nv_registry_new(const gchar **static_names, guint32 nvhandle_max_value)
128 {
129 NVRegistry *self = g_new0(NVRegistry, 1);
130 gint i;
131
132 self->nvhandle_max_value = nvhandle_max_value;
133 self->name_map = g_hash_table_new_full(g_str_hash, g_str_equal, g_free, NULL);
134 self->names = nvhandle_desc_array_new(NVHANDLE_DESC_ARRAY_INITIAL_SIZE);
135 for (i = 0; static_names[i]; i++)
136 {
137 nv_registry_alloc_handle(self, static_names[i]);
138 }
139 return self;
140 }
141
142 void
nv_registry_free(NVRegistry * self)143 nv_registry_free(NVRegistry *self)
144 {
145 nvhandle_desc_array_free(self->names);
146 g_hash_table_destroy(self->name_map);
147 g_free(self);
148 }
149
150 /* return the offset to a newly allocated payload string */
151 static inline NVEntry *
nv_table_alloc_value(NVTable * self,gsize alloc_size)152 nv_table_alloc_value(NVTable *self, gsize alloc_size)
153 {
154 NVEntry *entry;
155
156 alloc_size = NV_TABLE_BOUND(alloc_size);
157 /* alloc error, NVTable should be realloced */
158 if (!nv_table_alloc_check(self, alloc_size))
159 return NULL;
160 self->used += alloc_size;
161 entry = (NVEntry *) (nv_table_get_top(self) - (self->used));
162
163 /* initialize all flags to zero, so we don't need to bump the version for
164 * a compatible change */
165 entry->flags = 0;
166 entry->alloc_len = alloc_size;
167 entry->indirect = FALSE;
168 entry->referenced = FALSE;
169 entry->unset = FALSE;
170 return entry;
171 }
172
173 /* we only support single indirection */
174 const gchar *
nv_table_resolve_indirect(NVTable * self,NVEntry * entry,gssize * length)175 nv_table_resolve_indirect(NVTable *self, NVEntry *entry, gssize *length)
176 {
177 const gchar *referenced_value;
178 gssize referenced_length;
179
180 g_assert(entry->indirect);
181
182 referenced_value = nv_table_get_value(self, entry->vindirect.handle, &referenced_length);
183 if (entry->vindirect.ofs > referenced_length)
184 {
185 if (length)
186 *length = 0;
187 return null_string;
188 }
189
190 /* here we assume that indirect references are only looked up with
191 * non-zero terminated strings properly handled, thus the caller has
192 * to supply a non-NULL value_len */
193
194 g_assert(length != NULL);
195
196 *length = MIN(entry->vindirect.ofs + entry->vindirect.len, referenced_length) - entry->vindirect.ofs;
197 return referenced_value + entry->vindirect.ofs;
198 }
199
200 static inline const gchar *
nv_table_resolve_direct(NVTable * self,NVEntry * entry,gssize * length)201 nv_table_resolve_direct(NVTable *self, NVEntry *entry, gssize *length)
202 {
203 g_assert(!entry->indirect);
204
205 if (length)
206 *length = entry->vdirect.value_len;
207 return entry->vdirect.data + entry->name_len + 1;
208 }
209
210 static inline const gchar *
nv_table_resolve_entry(NVTable * self,NVEntry * entry,gssize * length)211 nv_table_resolve_entry(NVTable *self, NVEntry *entry, gssize *length)
212 {
213 if (entry->unset)
214 {
215 if (length)
216 *length = 0;
217 return null_string;
218 }
219 else if (entry->indirect)
220 return nv_table_resolve_indirect(self, entry, length);
221 else
222 return nv_table_resolve_direct(self, entry, length);
223 }
224
225 static inline NVIndexEntry *
_find_index_entry(NVIndexEntry * index_table,gint index_size,NVHandle handle,NVIndexEntry ** index_slot)226 _find_index_entry(NVIndexEntry *index_table, gint index_size, NVHandle handle, NVIndexEntry **index_slot)
227 {
228 gint l, h, m;
229 NVHandle mv;
230
231 /* short-cut, check if "handle" is larger than the last - sorted -
232 * element. If it is, we won't be finding it in this table. The loop
233 * below would conclude the same, but only after a log2(N) iterations */
234
235 if (index_size > 0 && index_table[index_size - 1].handle < handle)
236 {
237 *index_slot = &index_table[index_size];
238 return NULL;
239 }
240
241 /* open-coded binary search */
242 l = 0;
243 h = index_size - 1;
244 while (l <= h)
245 {
246 m = (l+h) >> 1;
247 mv = index_table[m].handle;
248 if (mv == handle)
249 {
250 *index_slot = &index_table[m];
251 return &index_table[m];
252 }
253 else if (mv > handle)
254 {
255 h = m - 1;
256 }
257 else
258 {
259 l = m + 1;
260 }
261 }
262 *index_slot = &index_table[l];
263 g_assert(l <= index_size);
264 return NULL;
265 }
266
267 /* slow path for nv_table_get_entry(), i.e. we need to perform the lookup
268 * for handle in the sorted index_table by implementing a binary search.
269 *
270 * The two output arguments `index_entry` and `index_slot` deserve further
271 * explanation:
272 * index_entry: points to the NVIndexEntry that referenced this NVEntry
273 *
274 * index_slot: points to the NVIndexEntry where a new element of this
275 * handle _should_ be inserted.
276 *
277 * This means that index_entry will be NULL if the handle is not present in
278 * this NVTable, whereas index_slot would point to the index_table element
279 * where we need to insert the new index_entry.
280 *
281 * In case the handle is present in NVTable, both index_entry and index_slot
282 * will point to the same location.
283 */
284
285 NVEntry *
nv_table_get_entry_slow(NVTable * self,NVHandle handle,NVIndexEntry ** index_entry,NVIndexEntry ** index_slot)286 nv_table_get_entry_slow(NVTable *self, NVHandle handle, NVIndexEntry **index_entry, NVIndexEntry **index_slot)
287 {
288 *index_entry = _find_index_entry(nv_table_get_index(self), self->index_size, handle, index_slot);
289 if (*index_entry)
290 return nv_table_get_entry_at_ofs(self, (*index_entry)->ofs);
291 return NULL;
292 }
293
294 static inline gboolean
_alloc_index_entry(NVTable * self,NVHandle handle,NVIndexEntry ** index_entry,NVIndexEntry * index_slot)295 _alloc_index_entry(NVTable *self, NVHandle handle, NVIndexEntry **index_entry, NVIndexEntry *index_slot)
296 {
297 if (G_UNLIKELY(!(*index_entry) && !nv_table_is_handle_static(self, handle)))
298 {
299 /* this is a dynamic value */
300 NVIndexEntry *index_table = nv_table_get_index(self);
301
302 if (!nv_table_alloc_check(self, sizeof(index_table[0])))
303 return FALSE;
304
305 NVIndexEntry *index_top = index_table + self->index_size;
306 if (index_slot != index_top)
307 {
308 /* move index entries up */
309 memmove(index_slot + 1, index_slot, (index_top - index_slot) * sizeof(index_table[0]));
310 }
311
312 *index_entry = index_slot;
313
314 /* we set ofs to zero here, which means that the NVEntry won't
315 be found even if the slot is present in index */
316 (*index_entry)->handle = handle;
317 (*index_entry)->ofs = 0;
318 self->index_size++;
319 }
320 return TRUE;
321 }
322
323 static inline void
nv_table_set_table_entry(NVTable * self,NVHandle handle,guint32 ofs,NVIndexEntry * index_entry)324 nv_table_set_table_entry(NVTable *self, NVHandle handle, guint32 ofs, NVIndexEntry *index_entry)
325 {
326 if (G_LIKELY(nv_table_is_handle_static(self, handle)))
327 {
328 /* this is a statically allocated value, simply store the offset */
329 self->static_entries[handle-1] = ofs;
330 }
331 else
332 {
333 /* this is a dynamic value */
334 (*index_entry).handle = handle;
335 (*index_entry).ofs = ofs;
336 }
337 }
338
339 static gboolean
_make_entry_direct(NVHandle handle,NVEntry * entry,NVIndexEntry * index_entry,gpointer user_data)340 _make_entry_direct(NVHandle handle, NVEntry *entry, NVIndexEntry *index_entry, gpointer user_data)
341 {
342 NVTable *self = (NVTable *) (((gpointer *) user_data)[0]);
343 NVHandle ref_handle = GPOINTER_TO_UINT(((gpointer *) user_data)[1]);
344
345 if (entry->indirect && entry->vindirect.handle == ref_handle)
346 {
347 const gchar *value;
348 gssize value_len;
349
350 value = nv_table_resolve_indirect(self, entry, &value_len);
351 if (!nv_table_add_value(self, handle, entry->vindirect.name, entry->name_len, value, value_len, NULL))
352 {
353 /* nvtable full, but we can't realloc it ourselves,
354 * propagate this back as a failure of
355 * nv_table_add_value() */
356
357 return TRUE;
358 }
359 }
360 return FALSE;
361 }
362
363 static inline gboolean
nv_table_break_references_to_entry(NVTable * self,NVHandle handle,NVEntry * entry)364 nv_table_break_references_to_entry(NVTable *self, NVHandle handle, NVEntry *entry)
365 {
366 if (G_UNLIKELY(entry && !entry->indirect && entry->referenced))
367 {
368 gpointer data[2] = { self, GUINT_TO_POINTER((glong) handle) };
369
370 if (nv_table_foreach_entry(self, _make_entry_direct, data))
371 {
372 /* we had to stop iteration, which means that we were unable
373 * to allocate enough space for making indirect entries
374 * direct */
375 return FALSE;
376 }
377 }
378 return TRUE;
379 }
380
381 static inline void
_overwrite_with_a_direct_entry(NVTable * self,NVHandle handle,NVEntry * entry,const gchar * name,gsize name_len,const gchar * value,gsize value_len)382 _overwrite_with_a_direct_entry(NVTable *self, NVHandle handle, NVEntry *entry, const gchar *name, gsize name_len,
383 const gchar *value, gsize value_len)
384 {
385 gchar *dst;
386
387 /* this value already exists and the new value fits in the old space */
388 if (!entry->indirect)
389 {
390 dst = entry->vdirect.data + entry->name_len + 1;
391
392 entry->vdirect.value_len = value_len;
393 memmove(dst, value, value_len);
394 dst[value_len] = 0;
395 }
396 else
397 {
398 /* this was an indirect entry, convert it */
399 entry->indirect = 0;
400 entry->vdirect.value_len = value_len;
401
402 if (!nv_table_is_handle_static(self, handle))
403 {
404 /* we pick up the name_len from the entry as it may be static in which case name is not stored */
405 g_assert(entry->name_len == name_len);
406 memmove(entry->vdirect.data, name, name_len + 1);
407 }
408 else
409 {
410 /* the old entry didn't have a name, we won't add it either */
411 name_len = 0;
412 entry->vdirect.data[0] = 0;
413 }
414 memmove(entry->vdirect.data + name_len + 1, value, value_len);
415 entry->vdirect.data[entry->name_len + 1 + value_len] = 0;
416 }
417 entry->unset = FALSE;
418 }
419
420 gboolean
nv_table_add_value(NVTable * self,NVHandle handle,const gchar * name,gsize name_len,const gchar * value,gsize value_len,gboolean * new_entry)421 nv_table_add_value(NVTable *self, NVHandle handle, const gchar *name, gsize name_len, const gchar *value,
422 gsize value_len, gboolean *new_entry)
423 {
424 NVEntry *entry;
425 guint32 ofs;
426 NVIndexEntry *index_entry, *index_slot;
427
428 if (value_len > NV_TABLE_MAX_BYTES)
429 value_len = NV_TABLE_MAX_BYTES;
430 if (new_entry)
431 *new_entry = FALSE;
432 entry = nv_table_get_entry(self, handle, &index_entry, &index_slot);
433 if (!nv_table_break_references_to_entry(self, handle, entry))
434 return FALSE;
435
436 if (entry && entry->alloc_len >= NV_ENTRY_DIRECT_SIZE(entry->name_len, value_len))
437 {
438 _overwrite_with_a_direct_entry(self, handle, entry, name, name_len, value, value_len);
439 return TRUE;
440 }
441 else if (!entry && new_entry)
442 *new_entry = TRUE;
443
444 /* check if there's enough free space: size of the struct plus the
445 * size needed for a dynamic table slot */
446 if (!_alloc_index_entry(self, handle, &index_entry, index_slot))
447 return FALSE;
448
449 if (nv_table_is_handle_static(self, handle))
450 name_len = 0;
451
452 entry = nv_table_alloc_value(self, NV_ENTRY_DIRECT_SIZE(name_len, value_len));
453 if (G_UNLIKELY(!entry))
454 {
455 return FALSE;
456 }
457
458 ofs = nv_table_get_ofs_for_an_entry(self, entry);
459 entry->vdirect.value_len = value_len;
460 entry->name_len = name_len;
461 if (entry->name_len != 0)
462 {
463 /* we only store the name for dynamic values */
464 memmove(entry->vdirect.data, name, name_len + 1);
465 }
466 memmove(entry->vdirect.data + entry->name_len + 1, value, value_len);
467 entry->vdirect.data[entry->name_len + 1 + value_len] = 0;
468
469 nv_table_set_table_entry(self, handle, ofs, index_entry);
470 return TRUE;
471 }
472
473 gboolean
nv_table_unset_value(NVTable * self,NVHandle handle)474 nv_table_unset_value(NVTable *self, NVHandle handle)
475 {
476 NVIndexEntry *index_entry;
477 NVEntry *entry = nv_table_get_entry(self, handle, &index_entry, NULL);
478
479 if (!entry)
480 return TRUE;
481
482 if (!nv_table_break_references_to_entry(self, handle, entry))
483 return FALSE;
484
485 entry->unset = TRUE;
486
487 /* make sure the actual value is also set to the null_string just in case
488 * this message is serialized and then deserialized by an earlier
489 * syslog-ng version which does not support the unset flag */
490 if (entry->indirect)
491 {
492 entry->vindirect.ofs = 0;
493 entry->vindirect.len = 0;
494 }
495 else
496 {
497 entry->vdirect.value_len = 0;
498 entry->vdirect.data[entry->name_len + 1] = 0;
499 }
500 return TRUE;
501 }
502
503 static void
nv_table_set_indirect_entry(NVTable * self,NVHandle handle,NVEntry * entry,const gchar * name,gsize name_len,const NVReferencedSlice * referenced_slice)504 nv_table_set_indirect_entry(NVTable *self, NVHandle handle, NVEntry *entry, const gchar *name, gsize name_len,
505 const NVReferencedSlice *referenced_slice)
506 {
507 entry->vindirect.handle = referenced_slice->handle;
508 entry->vindirect.ofs = referenced_slice->ofs;
509 entry->vindirect.len = referenced_slice->len;
510 entry->vindirect.type = referenced_slice->type;
511
512 if (entry->indirect)
513 return;
514
515 /* previously a non-indirect entry, convert it */
516 entry->indirect = 1;
517
518 if (!nv_table_is_handle_static(self, handle))
519 {
520 entry->name_len = name_len;
521 memmove(entry->vindirect.name, name, name_len + 1);
522 }
523 else
524 {
525 entry->name_len = 0;
526 }
527 }
528
529 static gboolean
nv_table_copy_referenced_value(NVTable * self,NVEntry * ref_entry,NVHandle handle,const gchar * name,gsize name_len,NVReferencedSlice * ref_slice,gboolean * new_entry)530 nv_table_copy_referenced_value(NVTable *self, NVEntry *ref_entry, NVHandle handle, const gchar *name,
531 gsize name_len, NVReferencedSlice *ref_slice, gboolean *new_entry)
532 {
533
534 gssize ref_length;
535 const gchar *ref_value = nv_table_resolve_entry(self, ref_entry, &ref_length);
536
537 if (ref_slice->ofs > ref_length)
538 {
539 ref_slice->len = 0;
540 ref_slice->ofs = 0;
541 }
542 else
543 {
544 ref_slice->len = MIN(ref_slice->ofs + ref_slice->len, ref_length) - ref_slice->ofs;
545 }
546
547 return nv_table_add_value(self, handle, name, name_len, ref_value + ref_slice->ofs, ref_slice->len, new_entry);
548 }
549
550 gboolean
nv_table_add_value_indirect(NVTable * self,NVHandle handle,const gchar * name,gsize name_len,NVReferencedSlice * referenced_slice,gboolean * new_entry)551 nv_table_add_value_indirect(NVTable *self, NVHandle handle, const gchar *name, gsize name_len,
552 NVReferencedSlice *referenced_slice, gboolean *new_entry)
553 {
554 NVEntry *entry, *ref_entry;
555 NVIndexEntry *index_entry, *index_slot;
556 guint32 ofs;
557
558 if (new_entry)
559 *new_entry = FALSE;
560 ref_entry = nv_table_get_entry(self, referenced_slice->handle, NULL, NULL);
561
562 if ((ref_entry && ref_entry->indirect) || handle == referenced_slice->handle)
563 {
564 /* NOTE: uh-oh, the to-be-referenced value is already an indirect
565 * reference, this is not supported, copy the stuff */
566 return nv_table_copy_referenced_value(self, ref_entry, handle, name, name_len, referenced_slice, new_entry);
567 }
568
569 entry = nv_table_get_entry(self, handle, &index_entry, &index_slot);
570 if ((!entry && !new_entry && referenced_slice->len == 0) || !ref_entry)
571 {
572 /* we don't store zero length matches unless the caller is
573 * interested in whether a new entry was created. It is used by
574 * the SDATA support code to decide whether a previously
575 * not-present SDATA was set */
576
577 return TRUE;
578 }
579
580 if (!nv_table_break_references_to_entry(self, handle, entry))
581 return FALSE;
582
583 if (entry && (entry->alloc_len >= NV_ENTRY_INDIRECT_SIZE(name_len)))
584 {
585 /* this value already exists and the new reference fits in the old space */
586 nv_table_set_indirect_entry(self, handle, entry, name, name_len, referenced_slice);
587 ref_entry->referenced = TRUE;
588 return TRUE;
589 }
590 else if (!entry && new_entry)
591 {
592 *new_entry = TRUE;
593 }
594
595 if (!_alloc_index_entry(self, handle, &index_entry, index_slot))
596 return FALSE;
597 entry = nv_table_alloc_value(self, NV_ENTRY_INDIRECT_SIZE(name_len));
598 if (!entry)
599 {
600 return FALSE;
601 }
602
603 ofs = nv_table_get_ofs_for_an_entry(self, entry);
604
605 nv_table_set_indirect_entry(self, handle, entry, name, name_len, referenced_slice);
606 ref_entry->referenced = TRUE;
607
608 nv_table_set_table_entry(self, handle, ofs, index_entry);
609
610 return TRUE;
611 }
612
613 static gboolean
nv_table_call_foreach(NVHandle handle,NVEntry * entry,NVIndexEntry * index_entry,gpointer user_data)614 nv_table_call_foreach(NVHandle handle, NVEntry *entry, NVIndexEntry *index_entry, gpointer user_data)
615 {
616 NVTable *self = (NVTable *) ((gpointer *) user_data)[0];
617 NVRegistry *registry = (NVRegistry *) ((gpointer *) user_data)[1];
618 NVTableForeachFunc func = ((gpointer *) user_data)[2];
619 gpointer func_data = ((gpointer *) user_data)[3];
620 const gchar *value;
621 gssize value_len;
622
623 if (entry->unset)
624 return FALSE;
625 value = nv_table_resolve_entry(self, entry, &value_len);
626 return func(handle, nv_registry_get_handle_name(registry, handle, NULL), value, value_len, func_data);
627 }
628
629 gboolean
nv_table_foreach(NVTable * self,NVRegistry * registry,NVTableForeachFunc func,gpointer user_data)630 nv_table_foreach(NVTable *self, NVRegistry *registry, NVTableForeachFunc func, gpointer user_data)
631 {
632 gpointer data[4] = { self, registry, func, user_data };
633
634 return nv_table_foreach_entry(self, nv_table_call_foreach, data);
635 }
636
637 gboolean
nv_table_foreach_entry(NVTable * self,NVTableForeachEntryFunc func,gpointer user_data)638 nv_table_foreach_entry(NVTable *self, NVTableForeachEntryFunc func, gpointer user_data)
639 {
640 NVIndexEntry *index_table;
641 NVEntry *entry;
642 gint i;
643
644 for (i = 0; i < self->num_static_entries; i++)
645 {
646 entry = nv_table_get_entry_at_ofs(self, self->static_entries[i]);
647 if (!entry)
648 continue;
649
650 if (func(i + 1, entry, NULL, user_data))
651 return TRUE;
652 }
653
654 index_table = nv_table_get_index(self);
655 for (i = 0; i < self->index_size; i++)
656 {
657 entry = nv_table_get_entry_at_ofs(self, index_table[i].ofs);
658
659 if (!entry)
660 continue;
661
662 if (func(index_table[i].handle, entry, &index_table[i], user_data))
663 return TRUE;
664 }
665
666 return FALSE;
667 }
668
669 void
nv_table_init(NVTable * self,gsize alloc_length,gint num_static_entries)670 nv_table_init(NVTable *self, gsize alloc_length, gint num_static_entries)
671 {
672 g_assert(alloc_length <= NV_TABLE_MAX_BYTES);
673 self->size = alloc_length;
674 self->used = 0;
675 self->index_size = 0;
676 self->num_static_entries = num_static_entries;
677 self->ref_cnt = 1;
678 self->borrowed = FALSE;
679 memset(&self->static_entries[0], 0, self->num_static_entries * sizeof(self->static_entries[0]));
680 }
681
682 NVTable *
nv_table_new(gint num_static_entries,gint index_size_hint,gint init_length)683 nv_table_new(gint num_static_entries, gint index_size_hint, gint init_length)
684 {
685 NVTable *self;
686 gsize alloc_length;
687
688 alloc_length = nv_table_get_alloc_size(num_static_entries, index_size_hint, init_length);
689 self = (NVTable *) g_malloc(alloc_length);
690
691 nv_table_init(self, alloc_length, num_static_entries);
692 return self;
693 }
694
695 NVTable *
nv_table_init_borrowed(gpointer space,gsize space_len,gint num_static_entries)696 nv_table_init_borrowed(gpointer space, gsize space_len, gint num_static_entries)
697 {
698 NVTable *self = (NVTable *) space;
699
700 space_len &= ~3;
701 g_assert(space_len > num_static_entries * sizeof(self->static_entries[0]) + sizeof(NVTable));
702 nv_table_init(self, NV_TABLE_BOUND(space_len), num_static_entries);
703 self->borrowed = TRUE;
704 return self;
705 }
706
707 /* returns TRUE if successfully realloced, FALSE means that we're unable to grow */
708 gboolean
nv_table_realloc(NVTable * self,NVTable ** new)709 nv_table_realloc(NVTable *self, NVTable **new)
710 {
711 gsize old_size = self->size;
712 gsize new_size;
713
714 /* double the size of the current allocation */
715 new_size = ((gsize) self->size) << 1;
716 if (new_size > NV_TABLE_MAX_BYTES)
717 new_size = NV_TABLE_MAX_BYTES;
718 if (new_size == old_size)
719 return FALSE;
720
721 if (self->ref_cnt == 1 && !self->borrowed)
722 {
723 *new = self = g_realloc(self, new_size);
724
725 self->size = new_size;
726 /* move the downwards growing region to the end of the new buffer */
727 memmove(NV_TABLE_ADDR(self, self->size - self->used),
728 NV_TABLE_ADDR(self, old_size - self->used),
729 self->used);
730 }
731 else
732 {
733 *new = g_malloc(new_size);
734
735 /* we only copy the header first */
736 memcpy(*new, self, sizeof(NVTable) + self->num_static_entries * sizeof(self->static_entries[0]) + self->index_size *
737 sizeof(NVIndexEntry));
738 (*new)->ref_cnt = 1;
739 (*new)->borrowed = FALSE;
740 (*new)->size = new_size;
741
742 memmove(NV_TABLE_ADDR((*new), (*new)->size - (*new)->used),
743 NV_TABLE_ADDR(self, old_size - self->used),
744 self->used);
745
746 nv_table_unref(self);
747 }
748 return TRUE;
749 }
750
751 NVTable *
nv_table_ref(NVTable * self)752 nv_table_ref(NVTable *self)
753 {
754 self->ref_cnt++;
755 return self;
756 }
757
758 void
nv_table_unref(NVTable * self)759 nv_table_unref(NVTable *self)
760 {
761 if ((--self->ref_cnt == 0) && !self->borrowed)
762 {
763 g_free(self);
764 }
765 }
766
767 /**
768 * nv_table_clone:
769 * @self: payload to clone
770 * @additional_space: specifies how much additional space is needed in
771 * the newly allocated clone
772 *
773 **/
774 NVTable *
nv_table_clone(NVTable * self,gint additional_space)775 nv_table_clone(NVTable *self, gint additional_space)
776 {
777 NVTable *new;
778 gint new_size;
779
780 if (nv_table_get_bottom(self) - nv_table_get_ofs_table_top(self) < additional_space)
781 new_size = self->size;
782 else
783 new_size = self->size + (NV_TABLE_BOUND(additional_space));
784
785 if (new_size > NV_TABLE_MAX_BYTES)
786 new_size = NV_TABLE_MAX_BYTES;
787
788 new = g_malloc(new_size);
789 memcpy(new, self, sizeof(NVTable) + self->num_static_entries * sizeof(self->static_entries[0]) + self->index_size *
790 sizeof(NVIndexEntry));
791 new->size = new_size;
792 new->ref_cnt = 1;
793 new->borrowed = FALSE;
794
795 memcpy(NV_TABLE_ADDR(new, new->size - new->used),
796 NV_TABLE_ADDR(self, self->size - self->used),
797 self->used);
798
799 return new;
800 }
801
802
803 static gboolean
_compact_foreach_entry(NVHandle handle,NVEntry * entry,NVIndexEntry * index_entry,gpointer user_data)804 _compact_foreach_entry(NVHandle handle, NVEntry *entry, NVIndexEntry *index_entry, gpointer user_data)
805 {
806 gpointer *args = (gpointer *) user_data;
807 NVTable *old = (NVTable *) args[0];
808 NVTable *new = (NVTable *) args[1];
809 const gchar *value, *name;
810 gssize value_len, name_len;
811
812 /* unused entries are skipped */
813 if (entry->unset)
814 return FALSE;
815
816 if (entry->name_len)
817 {
818 /* non-builtin entries have their name stored in the origin NVTable, use that */
819 name = nv_entry_get_name(entry);
820 name_len = entry->name_len;
821 }
822 else
823 {
824 /* builtin entries don't have their name stored, but we won't store
825 * them either, so just set them to NULL/0 */
826 name = NULL;
827 name_len = 0;
828 }
829
830 if (!entry->indirect)
831 {
832 value = nv_table_resolve_direct(old, entry, &value_len);
833
834 gboolean value_successfully_added = nv_table_add_value(new, handle, name, name_len, value, value_len, NULL);
835 g_assert(value_successfully_added);
836 }
837 else
838 {
839 gboolean value_successfully_added = nv_table_add_value_indirect(new, handle, name, name_len, &entry->vindirect, NULL);
840 g_assert(value_successfully_added);
841 }
842
843 return FALSE;
844 }
845
846 NVTable *
nv_table_compact(NVTable * self)847 nv_table_compact(NVTable *self)
848 {
849 gint new_size = self->size;
850 NVTable *new = g_malloc(new_size);
851 gpointer args[2] = { self, new };
852
853 nv_table_init(new, new_size, self->num_static_entries);
854
855 nv_table_foreach_entry(self, _compact_foreach_entry, args);
856 return new;
857 }
858