1*08b48e0bSAndroid Build Coastguard Worker /* 2*08b48e0bSAndroid Build Coastguard Worker american fuzzy lop++ - prealloc a buffer to reuse small elements often 3*08b48e0bSAndroid Build Coastguard Worker ---------------------------------------------------------------------- 4*08b48e0bSAndroid Build Coastguard Worker 5*08b48e0bSAndroid Build Coastguard Worker Originally written by Michal Zalewski 6*08b48e0bSAndroid Build Coastguard Worker 7*08b48e0bSAndroid Build Coastguard Worker Now maintained by Marc Heuse <[email protected]>, 8*08b48e0bSAndroid Build Coastguard Worker Heiko Eißfeldt <[email protected]>, 9*08b48e0bSAndroid Build Coastguard Worker Andrea Fioraldi <[email protected]>, 10*08b48e0bSAndroid Build Coastguard Worker Dominik Maier <[email protected]> 11*08b48e0bSAndroid Build Coastguard Worker 12*08b48e0bSAndroid Build Coastguard Worker Copyright 2016, 2017 Google Inc. All rights reserved. 13*08b48e0bSAndroid Build Coastguard Worker Copyright 2019-2024 AFLplusplus Project. All rights reserved. 14*08b48e0bSAndroid Build Coastguard Worker 15*08b48e0bSAndroid Build Coastguard Worker Licensed under the Apache License, Version 2.0 (the "License"); 16*08b48e0bSAndroid Build Coastguard Worker you may not use this file except in compliance with the License. 17*08b48e0bSAndroid Build Coastguard Worker You may obtain a copy of the License at: 18*08b48e0bSAndroid Build Coastguard Worker 19*08b48e0bSAndroid Build Coastguard Worker https://www.apache.org/licenses/LICENSE-2.0 20*08b48e0bSAndroid Build Coastguard Worker 21*08b48e0bSAndroid Build Coastguard Worker */ 22*08b48e0bSAndroid Build Coastguard Worker 23*08b48e0bSAndroid Build Coastguard Worker /* If we know we'll reuse small elements often, we'll just preallocate a buffer, 24*08b48e0bSAndroid Build Coastguard Worker * then fall back to malloc */ 25*08b48e0bSAndroid Build Coastguard Worker // TODO: Replace free status check with bitmask+CLZ 26*08b48e0bSAndroid Build Coastguard Worker 27*08b48e0bSAndroid Build Coastguard Worker #ifndef AFL_PREALLOC_H 28*08b48e0bSAndroid Build Coastguard Worker #define AFL_PREALLOC_H 29*08b48e0bSAndroid Build Coastguard Worker 30*08b48e0bSAndroid Build Coastguard Worker #include <stdio.h> 31*08b48e0bSAndroid Build Coastguard Worker #include <stdbool.h> 32*08b48e0bSAndroid Build Coastguard Worker #include <string.h> 33*08b48e0bSAndroid Build Coastguard Worker 34*08b48e0bSAndroid Build Coastguard Worker #include "debug.h" 35*08b48e0bSAndroid Build Coastguard Worker #include "alloc-inl.h" 36*08b48e0bSAndroid Build Coastguard Worker 37*08b48e0bSAndroid Build Coastguard Worker typedef enum prealloc_status { 38*08b48e0bSAndroid Build Coastguard Worker 39*08b48e0bSAndroid Build Coastguard Worker PRE_STATUS_UNUSED = 0, /* free in buf */ 40*08b48e0bSAndroid Build Coastguard Worker PRE_STATUS_USED, /* used in buf */ 41*08b48e0bSAndroid Build Coastguard Worker PRE_STATUS_MALLOC /* system malloc */ 42*08b48e0bSAndroid Build Coastguard Worker 43*08b48e0bSAndroid Build Coastguard Worker } pre_status_t; 44*08b48e0bSAndroid Build Coastguard Worker 45*08b48e0bSAndroid Build Coastguard Worker /* Adds the entry used for prealloc bookkeeping to this struct */ 46*08b48e0bSAndroid Build Coastguard Worker 47*08b48e0bSAndroid Build Coastguard Worker /* prealloc status of this instance */ 48*08b48e0bSAndroid Build Coastguard Worker #define PREALLOCABLE pre_status_t pre_status 49*08b48e0bSAndroid Build Coastguard Worker 50*08b48e0bSAndroid Build Coastguard Worker /* allocate an element of type *el_ptr, to this variable. 51*08b48e0bSAndroid Build Coastguard Worker Uses (and reuses) the given prealloc_buf before hitting libc's malloc. 52*08b48e0bSAndroid Build Coastguard Worker prealloc_buf must be the pointer to an array with type `type`. 53*08b48e0bSAndroid Build Coastguard Worker `type` must be a struct with uses PREALLOCABLE (a pre_status_t pre_status 54*08b48e0bSAndroid Build Coastguard Worker member). prealloc_size must be the array size. prealloc_counter must be a 55*08b48e0bSAndroid Build Coastguard Worker variable initialized with 0 (of any name). 56*08b48e0bSAndroid Build Coastguard Worker */ 57*08b48e0bSAndroid Build Coastguard Worker 58*08b48e0bSAndroid Build Coastguard Worker #define PRE_ALLOC(el_ptr, prealloc_buf, prealloc_size, prealloc_counter) \ 59*08b48e0bSAndroid Build Coastguard Worker do { \ 60*08b48e0bSAndroid Build Coastguard Worker \ 61*08b48e0bSAndroid Build Coastguard Worker if ((prealloc_counter) >= (prealloc_size)) { \ 62*08b48e0bSAndroid Build Coastguard Worker \ 63*08b48e0bSAndroid Build Coastguard Worker el_ptr = (element_t *)malloc(sizeof(*el_ptr)); \ 64*08b48e0bSAndroid Build Coastguard Worker if (!el_ptr) { FATAL("error in list.h -> out of memory for element!"); } \ 65*08b48e0bSAndroid Build Coastguard Worker el_ptr->pre_status = PRE_STATUS_MALLOC; \ 66*08b48e0bSAndroid Build Coastguard Worker \ 67*08b48e0bSAndroid Build Coastguard Worker } else { \ 68*08b48e0bSAndroid Build Coastguard Worker \ 69*08b48e0bSAndroid Build Coastguard Worker /* Find one of our preallocated elements */ \ 70*08b48e0bSAndroid Build Coastguard Worker u32 i; \ 71*08b48e0bSAndroid Build Coastguard Worker for (i = 0; i < (prealloc_size); i++) { \ 72*08b48e0bSAndroid Build Coastguard Worker \ 73*08b48e0bSAndroid Build Coastguard Worker el_ptr = &((prealloc_buf)[i]); \ 74*08b48e0bSAndroid Build Coastguard Worker if (el_ptr->pre_status == PRE_STATUS_UNUSED) { \ 75*08b48e0bSAndroid Build Coastguard Worker \ 76*08b48e0bSAndroid Build Coastguard Worker (prealloc_counter)++; \ 77*08b48e0bSAndroid Build Coastguard Worker el_ptr->pre_status = PRE_STATUS_USED; \ 78*08b48e0bSAndroid Build Coastguard Worker break; \ 79*08b48e0bSAndroid Build Coastguard Worker \ 80*08b48e0bSAndroid Build Coastguard Worker } \ 81*08b48e0bSAndroid Build Coastguard Worker \ 82*08b48e0bSAndroid Build Coastguard Worker } \ 83*08b48e0bSAndroid Build Coastguard Worker \ 84*08b48e0bSAndroid Build Coastguard Worker } \ 85*08b48e0bSAndroid Build Coastguard Worker \ 86*08b48e0bSAndroid Build Coastguard Worker if (!el_ptr) { FATAL("BUG in list.h -> no element found or allocated!"); } \ 87*08b48e0bSAndroid Build Coastguard Worker \ 88*08b48e0bSAndroid Build Coastguard Worker } while (0); 89*08b48e0bSAndroid Build Coastguard Worker 90*08b48e0bSAndroid Build Coastguard Worker /* Take a chosen (free) element from the prealloc_buf directly */ 91*08b48e0bSAndroid Build Coastguard Worker 92*08b48e0bSAndroid Build Coastguard Worker #define PRE_ALLOC_FORCE(el_ptr, prealloc_counter) \ 93*08b48e0bSAndroid Build Coastguard Worker do { \ 94*08b48e0bSAndroid Build Coastguard Worker \ 95*08b48e0bSAndroid Build Coastguard Worker if ((el_ptr)->pre_status != PRE_STATUS_UNUSED) { \ 96*08b48e0bSAndroid Build Coastguard Worker \ 97*08b48e0bSAndroid Build Coastguard Worker FATAL("PRE_ALLOC_FORCE element already allocated"); \ 98*08b48e0bSAndroid Build Coastguard Worker \ 99*08b48e0bSAndroid Build Coastguard Worker } \ 100*08b48e0bSAndroid Build Coastguard Worker (el_ptr)->pre_status = PRE_STATUS_USED; \ 101*08b48e0bSAndroid Build Coastguard Worker (prealloc_counter)++; \ 102*08b48e0bSAndroid Build Coastguard Worker \ 103*08b48e0bSAndroid Build Coastguard Worker } while (0); 104*08b48e0bSAndroid Build Coastguard Worker 105*08b48e0bSAndroid Build Coastguard Worker /* free an preallocated element */ 106*08b48e0bSAndroid Build Coastguard Worker 107*08b48e0bSAndroid Build Coastguard Worker #define PRE_FREE(el_ptr, prealloc_counter) \ 108*08b48e0bSAndroid Build Coastguard Worker do { \ 109*08b48e0bSAndroid Build Coastguard Worker \ 110*08b48e0bSAndroid Build Coastguard Worker switch ((el_ptr)->pre_status) { \ 111*08b48e0bSAndroid Build Coastguard Worker \ 112*08b48e0bSAndroid Build Coastguard Worker case PRE_STATUS_USED: { \ 113*08b48e0bSAndroid Build Coastguard Worker \ 114*08b48e0bSAndroid Build Coastguard Worker (el_ptr)->pre_status = PRE_STATUS_UNUSED; \ 115*08b48e0bSAndroid Build Coastguard Worker (prealloc_counter)--; \ 116*08b48e0bSAndroid Build Coastguard Worker if ((prealloc_counter) < 0) { \ 117*08b48e0bSAndroid Build Coastguard Worker \ 118*08b48e0bSAndroid Build Coastguard Worker FATAL("Inconsistent data in PRE_FREE"); \ 119*08b48e0bSAndroid Build Coastguard Worker \ 120*08b48e0bSAndroid Build Coastguard Worker } \ 121*08b48e0bSAndroid Build Coastguard Worker break; \ 122*08b48e0bSAndroid Build Coastguard Worker \ 123*08b48e0bSAndroid Build Coastguard Worker } \ 124*08b48e0bSAndroid Build Coastguard Worker case PRE_STATUS_MALLOC: { \ 125*08b48e0bSAndroid Build Coastguard Worker \ 126*08b48e0bSAndroid Build Coastguard Worker (el_ptr)->pre_status = PRE_STATUS_UNUSED; \ 127*08b48e0bSAndroid Build Coastguard Worker DFL_ck_free((el_ptr)); \ 128*08b48e0bSAndroid Build Coastguard Worker break; \ 129*08b48e0bSAndroid Build Coastguard Worker \ 130*08b48e0bSAndroid Build Coastguard Worker } \ 131*08b48e0bSAndroid Build Coastguard Worker default: { \ 132*08b48e0bSAndroid Build Coastguard Worker \ 133*08b48e0bSAndroid Build Coastguard Worker FATAL("Double Free Detected"); \ 134*08b48e0bSAndroid Build Coastguard Worker break; \ 135*08b48e0bSAndroid Build Coastguard Worker \ 136*08b48e0bSAndroid Build Coastguard Worker } \ 137*08b48e0bSAndroid Build Coastguard Worker \ 138*08b48e0bSAndroid Build Coastguard Worker } \ 139*08b48e0bSAndroid Build Coastguard Worker \ 140*08b48e0bSAndroid Build Coastguard Worker } while (0); 141*08b48e0bSAndroid Build Coastguard Worker 142*08b48e0bSAndroid Build Coastguard Worker #endif 143*08b48e0bSAndroid Build Coastguard Worker 144