Coverage Report

Created: 2023-12-08 06:56

/src/freeradius-server/src/lib/util/heap.c
Line
Count
Source (jump to first uncovered line)
1
/*
2
 *   This program is free software; you can redistribute it and/or modify
3
 *   it under the terms of the GNU General Public License as published by
4
 *   the Free Software Foundation; either version 2 of the License, or
5
 *   (at your option) any later version.
6
 *
7
 *   This program is distributed in the hope that it will be useful,
8
 *   but WITHOUT ANY WARRANTY; without even the implied warranty of
9
 *   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
10
 *   GNU General Public License for more details.
11
 *
12
 *   You should have received a copy of the GNU General Public License
13
 *   along with this program; if not, write to the Free Software
14
 *   Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301, USA
15
 */
16
17
/** Functions for a basic binary heaps
18
 *
19
 * @file src/lib/util/heap.c
20
 *
21
 * @copyright 2005,2006 The FreeRADIUS server project
22
 */
23
RCSID("$Id: 2e4c500dc484a79b6673fbd84284744521ecd5e3 $")
24
25
#define _HEAP_PRIVATE 1
26
#include <freeradius-devel/util/debug.h>
27
#include <freeradius-devel/util/heap.h>
28
#include <freeradius-devel/util/misc.h>
29
#include <freeradius-devel/util/strerror.h>
30
31
0
#define INITIAL_CAPACITY  2048
32
33
/*
34
 *  First node in a heap is element 1. Children of i are 2i and
35
 *  2i+1.  These macros wrap the logic, so the code is more
36
 *  descriptive.
37
 */
38
0
#define HEAP_PARENT(_x) ((_x) >> 1)
39
0
#define HEAP_LEFT(_x) (2 * (_x))
40
0
#define HEAP_RIGHT(_x) (2 * (_x) + 1 )
41
0
#define HEAP_SWAP(_a, _b) do { void *_tmp = _a; _a = _b; _b = _tmp; } while (0)
42
43
static void fr_heap_bubble(fr_heap_t *h, fr_heap_index_t child);
44
45
/** Return how many bytes need to be allocated to hold a heap of a given size
46
 *
47
 * This is useful for passing to talloc[_zero]_pooled_object to avoid additional mallocs.
48
 *
49
 * @param[in] count The initial element count.
50
 * @return The number of bytes to pre-allocate.
51
 */
52
size_t fr_heap_pre_alloc_size(unsigned int count)
53
0
{
54
0
  return sizeof(fr_heap_t) + sizeof(void *) * count;
55
0
}
56
57
fr_heap_t *_fr_heap_alloc(TALLOC_CTX *ctx, fr_heap_cmp_t cmp, char const *type, size_t offset, unsigned int init)
58
0
{
59
0
  fr_heap_t *h;
60
61
0
  if (!init) init = INITIAL_CAPACITY;
62
63
  /*
64
   *  For small heaps (< 40 elements) the
65
   *  increase in memory locality gives us
66
   *  a 100% performance increase
67
   *  (talloc headers are big);
68
   */
69
0
  h = (fr_heap_t *)talloc_array(ctx, uint8_t, sizeof(fr_heap_t) + (sizeof(void *) * (init + 1)));
70
0
  if (unlikely(!h)) return NULL;
71
0
  talloc_set_type(h, fr_heap_t);
72
73
0
  *h = (fr_heap_t){
74
0
    .size = init,
75
0
    .min = init,
76
0
    .type = type,
77
0
    .cmp = cmp,
78
0
    .offset = offset
79
0
  };
80
81
  /*
82
   *  As we're using unsigned index values
83
   *      index 0 is a special value meaning
84
   *      that the data isn't currently inserted
85
   *  into the heap.
86
   */
87
0
  h->p[0] = (void *)UINTPTR_MAX;
88
89
0
  return h;
90
0
}
91
92
static inline CC_HINT(always_inline, nonnull) fr_heap_index_t index_get(fr_heap_t *h, void *data)
93
0
{
94
0
  return *((fr_heap_index_t const *)(((uint8_t const *)data) + h->offset));
95
0
}
96
97
static inline CC_HINT(always_inline, nonnull) void index_set(fr_heap_t *h, void *data, fr_heap_index_t idx)
98
0
{
99
0
  *((fr_heap_index_t *)(((uint8_t *)data) + h->offset)) = idx;
100
0
}
101
102
0
#define OFFSET_SET(_heap, _idx) index_set(_heap, _heap->p[_idx], _idx)
103
0
#define OFFSET_RESET(_heap, _idx) index_set(_heap, _heap->p[_idx], 0)
104
105
static inline CC_HINT(always_inline)
106
int realloc_heap(fr_heap_t **hp, unsigned int n_size)
107
0
{
108
0
  fr_heap_t *h = *hp;
109
110
0
  h = (fr_heap_t *)talloc_realloc(hp, h, uint8_t, sizeof(fr_heap_t) + (sizeof(void *) * (n_size + 1)));
111
0
  if (unlikely(!h)) {
112
0
    fr_strerror_printf("Failed expanding heap to %u elements (%u bytes)",
113
0
           n_size, (n_size * (unsigned int)sizeof(void *)));
114
0
    return -1;
115
0
  }
116
0
  talloc_set_type(h, fr_heap_t);
117
0
  h->size = n_size;
118
119
0
  *hp = h;
120
121
0
  return 0;
122
0
}
123
124
125
/** Insert a new element into the heap
126
 *
127
 * Insert element in heap. Normally, p != NULL, we insert p in a
128
 * new position and bubble up. If p == NULL, then the element is
129
 * already in place, and key is the position where to start the
130
 * bubble-up.
131
 *
132
 * Returns -1 on failure (cannot allocate new heap entry)
133
 *
134
 * If offset > 0 the position (index, int) of the element in the
135
 * heap is also stored in the element itself at the given offset
136
 * in bytes.
137
 *
138
 * @param[in,out] hp  The heap to extract an element from.
139
 *      A new pointer value will be written to hp
140
 *      if the heap is resized.
141
 * @param[in] data  Data to insert into the heap.
142
 * @return
143
 *  - 0 on success.
144
 *  - -1 on failure (heap full or malloc error).
145
 */
146
int fr_heap_insert(fr_heap_t **hp, void *data)
147
0
{
148
0
  fr_heap_t *h = *hp;
149
0
  fr_heap_index_t child;
150
151
0
  if (unlikely(h == NULL)) {
152
0
    fr_strerror_const("Heap pointer was NULL");
153
0
    return -1;
154
0
  }
155
156
0
  child = index_get(h, data);
157
0
  if (fr_heap_entry_inserted(child)) {
158
0
    fr_strerror_const("Node is already in the heap");
159
0
    return -1;
160
0
  }
161
162
0
  child = h->num_elements + 1;  /* Avoid using index 0 */
163
164
0
#ifndef TALLOC_GET_TYPE_ABORT_NOOP
165
0
  if (h->type) (void)_talloc_get_type_abort(data, h->type, __location__);
166
0
#endif
167
168
  /*
169
   *  Heap is full.  Double it's size.
170
   */
171
0
  if (child > h->size) {
172
0
    unsigned int  n_size;
173
174
    /*
175
     *  heap_id is a 32-bit unsigned integer.  If the heap will
176
     *  grow to contain more than 4B elements, disallow
177
     *  integer overflow.  Tho TBH, that should really never
178
     *  happen.
179
     */
180
0
    if (unlikely(h->size > (UINT_MAX - h->size))) {
181
0
      if (h->size == UINT_MAX) {
182
0
        fr_strerror_const("Heap is full");
183
0
        return -1;
184
0
      } else {
185
0
        n_size = UINT_MAX;
186
0
      }
187
0
    } else {
188
0
      n_size = h->size * 2;
189
0
    }
190
191
0
    if (realloc_heap(&h, n_size) < 0) return -1;
192
193
0
    *hp = h;
194
0
  }
195
196
0
  h->p[child] = data;
197
0
  h->num_elements++;
198
199
0
  fr_heap_bubble(h, child);
200
201
0
  return 0;
202
0
}
203
204
static inline CC_HINT(always_inline) void fr_heap_bubble(fr_heap_t *h, fr_heap_index_t child)
205
0
{
206
0
  if (!fr_cond_assert(child != FR_HEAP_INDEX_INVALID)) return;
207
208
  /*
209
   *  Bubble up the element.
210
   */
211
0
  while (child > 1) {
212
0
    fr_heap_index_t parent = HEAP_PARENT(child);
213
214
    /*
215
     *  Parent is smaller than the child.  We're done.
216
     */
217
0
    if (h->cmp(h->p[parent], h->p[child]) < 0) break;
218
219
    /*
220
     *  Child is smaller than the parent, repeat.
221
     */
222
0
    HEAP_SWAP(h->p[child], h->p[parent]);
223
0
    OFFSET_SET(h, child);
224
0
    child = parent;
225
0
  }
226
0
  OFFSET_SET(h, child);
227
0
}
228
229
/** Remove a node from the heap
230
 *
231
 * @param[in,out] hp  The heap to extract an element from.
232
 *      A new pointer value will be written to hp
233
 *      if the heap is resized.
234
 * @param[in] data  Data to extract from the heap.
235
 * @return
236
 *  - 0 on success.
237
 *  - -1 on failure (no elements or data not found).
238
 */
239
int fr_heap_extract(fr_heap_t **hp, void *data)
240
0
{
241
0
  fr_heap_t *h = *hp;
242
0
  fr_heap_index_t parent, child, max;
243
244
0
  if (unlikely(h == NULL)) {
245
0
    fr_strerror_const("Heap pointer was NULL");
246
0
    return -1;
247
0
  }
248
249
  /*
250
   *  Extract element.
251
   */
252
0
  parent = index_get(h, data);
253
254
  /*
255
   *  Out of bounds.
256
   */
257
0
  if (unlikely((parent == 0) || (parent > h->num_elements))) {
258
0
    fr_strerror_printf("Heap parent (%i) out of bounds (0-%i)", parent, h->num_elements);
259
0
    return -1;
260
0
  }
261
262
0
  if (unlikely(data != h->p[parent])) {
263
0
    fr_strerror_printf("Invalid heap index.  Expected data %p at offset %i, got %p", data,
264
0
           parent, h->p[parent]);
265
0
    return -1;
266
0
  }
267
0
  max = h->num_elements;
268
269
0
  child = HEAP_LEFT(parent);
270
0
  OFFSET_RESET(h, parent);
271
0
  while (child <= max) {
272
    /*
273
     *  Maybe take the right child.
274
     */
275
0
    if ((child != max) &&
276
0
        (h->cmp(h->p[child + 1], h->p[child]) < 0)) {
277
0
      child = child + 1;
278
0
    }
279
0
    h->p[parent] = h->p[child];
280
0
    OFFSET_SET(h, parent);
281
0
    parent = child;
282
0
    child = HEAP_LEFT(child);
283
0
  }
284
0
  h->num_elements--;
285
286
  /*
287
   *  If the number of elements in the heap is half
288
   *  what we need, shrink the heap back.
289
   */
290
0
  if ((h->num_elements * 2) < h->size) {
291
0
    unsigned int n_size = ROUND_UP_DIV(h->size, 2);
292
293
0
    if ((n_size > h->min) && (realloc_heap(&h, n_size)) == 0) *hp = h;
294
0
  }
295
296
  /*
297
   *  We didn't end up at the last element in the heap.
298
   *  This element has to be re-inserted.
299
   */
300
0
  if (parent != max) {
301
    /*
302
     *  Fill hole with last entry and bubble up,
303
     *  reusing the insert code
304
     */
305
0
    h->p[parent] = h->p[max];
306
307
0
    fr_heap_bubble(h, parent);
308
0
  }
309
310
0
  return 0;
311
0
}
312
313
/** Remove a node from the heap
314
 *
315
 * @param[in,out] hp  The heap to pop an element from.
316
 *      A new pointer value will be written to hp
317
 *      if the heap is resized.
318
 * @return
319
 *      - The item that was popped.
320
 *  - NULL on error.
321
 */
322
void *fr_heap_pop(fr_heap_t **hp)
323
0
{
324
0
  fr_heap_t *h = *hp;
325
0
  void *data;
326
327
0
  if (unlikely(h == NULL)) {
328
0
    fr_strerror_const("Heap pointer was NULL");
329
0
    return NULL;
330
0
  }
331
332
0
  if (h->num_elements == 0) return NULL;
333
334
0
  data = h->p[1];
335
0
  if (unlikely(fr_heap_extract(hp, data) < 0)) return NULL;
336
337
0
  return data;
338
0
}
339
340
/** Iterate over entries in heap
341
 *
342
 * @note If the heap is modified the iterator should be considered invalidated.
343
 *
344
 * @param[in] h   to iterate over.
345
 * @param[in] iter  Pointer to an iterator struct, used to maintain
346
 *      state between calls.
347
 * @return
348
 *  - User data.
349
 *  - NULL if at the end of the list.
350
 */
351
void *fr_heap_iter_init(fr_heap_t *h, fr_heap_iter_t *iter)
352
0
{
353
0
  *iter = 1;
354
355
0
  if (h->num_elements == 0) return NULL;
356
357
0
  return h->p[1];
358
0
}
359
360
/** Get the next entry in a heap
361
 *
362
 * @note If the heap is modified the iterator should be considered invalidated.
363
 *
364
 * @param[in] h   to iterate over.
365
 * @param[in] iter  Pointer to an iterator struct, used to maintain
366
 *      state between calls.
367
 * @return
368
 *  - User data.
369
 *  - NULL if at the end of the list.
370
 */
371
void *fr_heap_iter_next(fr_heap_t *h, fr_heap_iter_t *iter)
372
0
{
373
0
  if ((*iter + 1) > h->num_elements) return NULL;
374
0
  *iter += 1;
375
376
0
  return h->p[*iter];
377
0
}
378
379
#ifndef TALLOC_GET_TYPE_ABORT_NOOP
380
void fr_heap_verify(char const *file, int line, fr_heap_t *h)
381
0
{
382
0
  fr_fatal_assert_msg(h, "CONSISTENCY CHECK FAILED %s[%i]: fr_heap_t pointer was NULL", file, line);
383
0
  (void) talloc_get_type_abort(h, fr_heap_t);
384
385
  /*
386
   *  Allocating the heap structure and the array holding the heap as described in data structure
387
   *  texts together is a respectable savings, but it means adding a level of indirection so the
388
   *  fr_heap_t * isn't realloc()ed out from under the user, hence the following (and the use of h
389
   *  rather than hp to access anything in the heap structure).
390
   */
391
0
  fr_fatal_assert_msg(h, "CONSISTENCY CHECK FAILED %s[%i]: heap_t pointer was NULL", file, line);
392
0
  (void) talloc_get_type_abort(h, fr_heap_t);
393
394
0
  fr_fatal_assert_msg(h->num_elements <= h->size,
395
0
          "CONSISTENCY CHECK FAILED %s[%i]: num_elements exceeds size", file, line);
396
397
0
  fr_fatal_assert_msg(h->p[0] == (void *)UINTPTR_MAX,
398
0
          "CONSISTENCY CHECK FAILED %s[%i]: zeroeth element special value overwritten", file, line);
399
400
0
  for (unsigned int i = 1; i <= h->num_elements; i++) {
401
0
    void  *data = h->p[i];
402
403
0
    fr_fatal_assert_msg(data, "CONSISTENCY CHECK FAILED %s[%i]: node %u was NULL", file, line, i);
404
0
    if (h->type) (void)_talloc_get_type_abort(data, h->type, __location__);
405
0
    fr_fatal_assert_msg(index_get(h, data) == i,
406
0
            "CONSISTENCY CHECK FAILED %s[%i]: node %u index != %u", file, line, i, i);
407
0
  }
408
0
  for (unsigned int i = 1; ; i++) {
409
0
    if (HEAP_LEFT(i) > h->num_elements) break;
410
0
    fr_fatal_assert_msg(h->cmp(h->p[i], h->p[HEAP_LEFT(i)]) <= 0,
411
0
            "CONSISTENCY_CHECK_FAILED %s[%i]: node %u > left child", file, line, i);
412
0
    if (HEAP_RIGHT(i) > h->num_elements) break;
413
0
    fr_fatal_assert_msg(h->cmp(h->p[i], h->p[HEAP_RIGHT(i)]) <= 0,
414
0
            "CONSISTENCY_CHECK_FAILED %s[%i]: node %u > right child", file, line, i);
415
0
  }
416
0
}
417
#endif