1233d2500723e5594f3e7c70896ffeeef32b9c950ywan/* 2233d2500723e5594f3e7c70896ffeeef32b9c950ywan * Copyright (c) 2004i-2010 Alex Pankratov. All rights reserved. 3233d2500723e5594f3e7c70896ffeeef32b9c950ywan * 4233d2500723e5594f3e7c70896ffeeef32b9c950ywan * Hierarchical memory allocator, 1.2.1 5233d2500723e5594f3e7c70896ffeeef32b9c950ywan * http://swapped.cc/halloc 6233d2500723e5594f3e7c70896ffeeef32b9c950ywan */ 7233d2500723e5594f3e7c70896ffeeef32b9c950ywan 8233d2500723e5594f3e7c70896ffeeef32b9c950ywan/* 9233d2500723e5594f3e7c70896ffeeef32b9c950ywan * The program is distributed under terms of BSD license. 10233d2500723e5594f3e7c70896ffeeef32b9c950ywan * You can obtain the copy of the license by visiting: 11233d2500723e5594f3e7c70896ffeeef32b9c950ywan * 12233d2500723e5594f3e7c70896ffeeef32b9c950ywan * http://www.opensource.org/licenses/bsd-license.php 13233d2500723e5594f3e7c70896ffeeef32b9c950ywan */ 14233d2500723e5594f3e7c70896ffeeef32b9c950ywan 15233d2500723e5594f3e7c70896ffeeef32b9c950ywan#include <stdlib.h> /* realloc */ 16233d2500723e5594f3e7c70896ffeeef32b9c950ywan#include <string.h> /* memset & co */ 17233d2500723e5594f3e7c70896ffeeef32b9c950ywan 18233d2500723e5594f3e7c70896ffeeef32b9c950ywan#include "third_party/nestegg/halloc/halloc.h" 19233d2500723e5594f3e7c70896ffeeef32b9c950ywan#include "align.h" 20233d2500723e5594f3e7c70896ffeeef32b9c950ywan#include "hlist.h" 21233d2500723e5594f3e7c70896ffeeef32b9c950ywan 22233d2500723e5594f3e7c70896ffeeef32b9c950ywan/* 23233d2500723e5594f3e7c70896ffeeef32b9c950ywan * block control header 24233d2500723e5594f3e7c70896ffeeef32b9c950ywan */ 25233d2500723e5594f3e7c70896ffeeef32b9c950ywantypedef struct hblock 26233d2500723e5594f3e7c70896ffeeef32b9c950ywan{ 27233d2500723e5594f3e7c70896ffeeef32b9c950ywan#ifndef NDEBUG 28233d2500723e5594f3e7c70896ffeeef32b9c950ywan#define HH_MAGIC 0x20040518L 29233d2500723e5594f3e7c70896ffeeef32b9c950ywan long magic; 30233d2500723e5594f3e7c70896ffeeef32b9c950ywan#endif 31233d2500723e5594f3e7c70896ffeeef32b9c950ywan hlist_item_t siblings; /* 2 pointers */ 32233d2500723e5594f3e7c70896ffeeef32b9c950ywan hlist_head_t children; /* 1 pointer */ 33233d2500723e5594f3e7c70896ffeeef32b9c950ywan max_align_t data[1]; /* not allocated, see below */ 34233d2500723e5594f3e7c70896ffeeef32b9c950ywan 35233d2500723e5594f3e7c70896ffeeef32b9c950ywan} hblock_t; 36233d2500723e5594f3e7c70896ffeeef32b9c950ywan 37233d2500723e5594f3e7c70896ffeeef32b9c950ywan#define sizeof_hblock offsetof(hblock_t, data) 38233d2500723e5594f3e7c70896ffeeef32b9c950ywan 39233d2500723e5594f3e7c70896ffeeef32b9c950ywan/* 40233d2500723e5594f3e7c70896ffeeef32b9c950ywan * 41233d2500723e5594f3e7c70896ffeeef32b9c950ywan */ 42233d2500723e5594f3e7c70896ffeeef32b9c950ywanrealloc_t halloc_allocator = NULL; 43233d2500723e5594f3e7c70896ffeeef32b9c950ywan 44233d2500723e5594f3e7c70896ffeeef32b9c950ywan#define allocator halloc_allocator 45233d2500723e5594f3e7c70896ffeeef32b9c950ywan 46233d2500723e5594f3e7c70896ffeeef32b9c950ywan/* 47233d2500723e5594f3e7c70896ffeeef32b9c950ywan * static methods 48233d2500723e5594f3e7c70896ffeeef32b9c950ywan */ 49233d2500723e5594f3e7c70896ffeeef32b9c950ywanstatic void _set_allocator(void); 50233d2500723e5594f3e7c70896ffeeef32b9c950ywanstatic void * _realloc(void * ptr, size_t n); 51233d2500723e5594f3e7c70896ffeeef32b9c950ywan 52233d2500723e5594f3e7c70896ffeeef32b9c950ywanstatic int _relate(hblock_t * b, hblock_t * p); 53233d2500723e5594f3e7c70896ffeeef32b9c950ywanstatic void _free_children(hblock_t * p); 54233d2500723e5594f3e7c70896ffeeef32b9c950ywan 55233d2500723e5594f3e7c70896ffeeef32b9c950ywan/* 56233d2500723e5594f3e7c70896ffeeef32b9c950ywan * Core API 57233d2500723e5594f3e7c70896ffeeef32b9c950ywan */ 58233d2500723e5594f3e7c70896ffeeef32b9c950ywanvoid * halloc(void * ptr, size_t len) 59233d2500723e5594f3e7c70896ffeeef32b9c950ywan{ 60233d2500723e5594f3e7c70896ffeeef32b9c950ywan hblock_t * p; 61233d2500723e5594f3e7c70896ffeeef32b9c950ywan 62233d2500723e5594f3e7c70896ffeeef32b9c950ywan /* set up default allocator */ 63233d2500723e5594f3e7c70896ffeeef32b9c950ywan if (! allocator) 64233d2500723e5594f3e7c70896ffeeef32b9c950ywan { 65233d2500723e5594f3e7c70896ffeeef32b9c950ywan _set_allocator(); 66233d2500723e5594f3e7c70896ffeeef32b9c950ywan assert(allocator); 67233d2500723e5594f3e7c70896ffeeef32b9c950ywan } 68233d2500723e5594f3e7c70896ffeeef32b9c950ywan 69233d2500723e5594f3e7c70896ffeeef32b9c950ywan /* calloc */ 70233d2500723e5594f3e7c70896ffeeef32b9c950ywan if (! ptr) 71233d2500723e5594f3e7c70896ffeeef32b9c950ywan { 72233d2500723e5594f3e7c70896ffeeef32b9c950ywan if (! len) 73233d2500723e5594f3e7c70896ffeeef32b9c950ywan return NULL; 74233d2500723e5594f3e7c70896ffeeef32b9c950ywan 75233d2500723e5594f3e7c70896ffeeef32b9c950ywan p = allocator(0, len + sizeof_hblock); 76233d2500723e5594f3e7c70896ffeeef32b9c950ywan if (! p) 77233d2500723e5594f3e7c70896ffeeef32b9c950ywan return NULL; 78233d2500723e5594f3e7c70896ffeeef32b9c950ywan#ifndef NDEBUG 79233d2500723e5594f3e7c70896ffeeef32b9c950ywan p->magic = HH_MAGIC; 80233d2500723e5594f3e7c70896ffeeef32b9c950ywan#endif 81233d2500723e5594f3e7c70896ffeeef32b9c950ywan hlist_init(&p->children); 82233d2500723e5594f3e7c70896ffeeef32b9c950ywan hlist_init_item(&p->siblings); 83233d2500723e5594f3e7c70896ffeeef32b9c950ywan 84233d2500723e5594f3e7c70896ffeeef32b9c950ywan return p->data; 85233d2500723e5594f3e7c70896ffeeef32b9c950ywan } 86233d2500723e5594f3e7c70896ffeeef32b9c950ywan 87233d2500723e5594f3e7c70896ffeeef32b9c950ywan p = structof(ptr, hblock_t, data); 88233d2500723e5594f3e7c70896ffeeef32b9c950ywan assert(p->magic == HH_MAGIC); 89233d2500723e5594f3e7c70896ffeeef32b9c950ywan 90233d2500723e5594f3e7c70896ffeeef32b9c950ywan /* realloc */ 91233d2500723e5594f3e7c70896ffeeef32b9c950ywan if (len) 92233d2500723e5594f3e7c70896ffeeef32b9c950ywan { 93233d2500723e5594f3e7c70896ffeeef32b9c950ywan p = allocator(p, len + sizeof_hblock); 94233d2500723e5594f3e7c70896ffeeef32b9c950ywan if (! p) 95233d2500723e5594f3e7c70896ffeeef32b9c950ywan return NULL; 96233d2500723e5594f3e7c70896ffeeef32b9c950ywan 97233d2500723e5594f3e7c70896ffeeef32b9c950ywan hlist_relink(&p->siblings); 98233d2500723e5594f3e7c70896ffeeef32b9c950ywan hlist_relink_head(&p->children); 99233d2500723e5594f3e7c70896ffeeef32b9c950ywan 100233d2500723e5594f3e7c70896ffeeef32b9c950ywan return p->data; 101233d2500723e5594f3e7c70896ffeeef32b9c950ywan } 102233d2500723e5594f3e7c70896ffeeef32b9c950ywan 103233d2500723e5594f3e7c70896ffeeef32b9c950ywan /* free */ 104233d2500723e5594f3e7c70896ffeeef32b9c950ywan _free_children(p); 105233d2500723e5594f3e7c70896ffeeef32b9c950ywan hlist_del(&p->siblings); 106233d2500723e5594f3e7c70896ffeeef32b9c950ywan allocator(p, 0); 107233d2500723e5594f3e7c70896ffeeef32b9c950ywan 108233d2500723e5594f3e7c70896ffeeef32b9c950ywan return NULL; 109233d2500723e5594f3e7c70896ffeeef32b9c950ywan} 110233d2500723e5594f3e7c70896ffeeef32b9c950ywan 111233d2500723e5594f3e7c70896ffeeef32b9c950ywanvoid hattach(void * block, void * parent) 112233d2500723e5594f3e7c70896ffeeef32b9c950ywan{ 113233d2500723e5594f3e7c70896ffeeef32b9c950ywan hblock_t * b, * p; 114233d2500723e5594f3e7c70896ffeeef32b9c950ywan 115233d2500723e5594f3e7c70896ffeeef32b9c950ywan if (! block) 116233d2500723e5594f3e7c70896ffeeef32b9c950ywan { 117233d2500723e5594f3e7c70896ffeeef32b9c950ywan assert(! parent); 118233d2500723e5594f3e7c70896ffeeef32b9c950ywan return; 119233d2500723e5594f3e7c70896ffeeef32b9c950ywan } 120233d2500723e5594f3e7c70896ffeeef32b9c950ywan 121233d2500723e5594f3e7c70896ffeeef32b9c950ywan /* detach */ 122233d2500723e5594f3e7c70896ffeeef32b9c950ywan b = structof(block, hblock_t, data); 123233d2500723e5594f3e7c70896ffeeef32b9c950ywan assert(b->magic == HH_MAGIC); 124233d2500723e5594f3e7c70896ffeeef32b9c950ywan 125233d2500723e5594f3e7c70896ffeeef32b9c950ywan hlist_del(&b->siblings); 126233d2500723e5594f3e7c70896ffeeef32b9c950ywan 127233d2500723e5594f3e7c70896ffeeef32b9c950ywan if (! parent) 128233d2500723e5594f3e7c70896ffeeef32b9c950ywan return; 129233d2500723e5594f3e7c70896ffeeef32b9c950ywan 130233d2500723e5594f3e7c70896ffeeef32b9c950ywan /* attach */ 131233d2500723e5594f3e7c70896ffeeef32b9c950ywan p = structof(parent, hblock_t, data); 132233d2500723e5594f3e7c70896ffeeef32b9c950ywan assert(p->magic == HH_MAGIC); 133233d2500723e5594f3e7c70896ffeeef32b9c950ywan 134233d2500723e5594f3e7c70896ffeeef32b9c950ywan /* sanity checks */ 135233d2500723e5594f3e7c70896ffeeef32b9c950ywan assert(b != p); /* trivial */ 136233d2500723e5594f3e7c70896ffeeef32b9c950ywan assert(! _relate(p, b)); /* heavy ! */ 137233d2500723e5594f3e7c70896ffeeef32b9c950ywan 138233d2500723e5594f3e7c70896ffeeef32b9c950ywan hlist_add(&p->children, &b->siblings); 139233d2500723e5594f3e7c70896ffeeef32b9c950ywan} 140233d2500723e5594f3e7c70896ffeeef32b9c950ywan 141233d2500723e5594f3e7c70896ffeeef32b9c950ywan/* 142233d2500723e5594f3e7c70896ffeeef32b9c950ywan * malloc/free api 143233d2500723e5594f3e7c70896ffeeef32b9c950ywan */ 144233d2500723e5594f3e7c70896ffeeef32b9c950ywanvoid * h_malloc(size_t len) 145233d2500723e5594f3e7c70896ffeeef32b9c950ywan{ 146233d2500723e5594f3e7c70896ffeeef32b9c950ywan return halloc(0, len); 147233d2500723e5594f3e7c70896ffeeef32b9c950ywan} 148233d2500723e5594f3e7c70896ffeeef32b9c950ywan 149233d2500723e5594f3e7c70896ffeeef32b9c950ywanvoid * h_calloc(size_t n, size_t len) 150233d2500723e5594f3e7c70896ffeeef32b9c950ywan{ 151233d2500723e5594f3e7c70896ffeeef32b9c950ywan void * ptr = halloc(0, len*=n); 152233d2500723e5594f3e7c70896ffeeef32b9c950ywan return ptr ? memset(ptr, 0, len) : NULL; 153233d2500723e5594f3e7c70896ffeeef32b9c950ywan} 154233d2500723e5594f3e7c70896ffeeef32b9c950ywan 155233d2500723e5594f3e7c70896ffeeef32b9c950ywanvoid * h_realloc(void * ptr, size_t len) 156233d2500723e5594f3e7c70896ffeeef32b9c950ywan{ 157233d2500723e5594f3e7c70896ffeeef32b9c950ywan return halloc(ptr, len); 158233d2500723e5594f3e7c70896ffeeef32b9c950ywan} 159233d2500723e5594f3e7c70896ffeeef32b9c950ywan 160233d2500723e5594f3e7c70896ffeeef32b9c950ywanvoid h_free(void * ptr) 161233d2500723e5594f3e7c70896ffeeef32b9c950ywan{ 162233d2500723e5594f3e7c70896ffeeef32b9c950ywan halloc(ptr, 0); 163233d2500723e5594f3e7c70896ffeeef32b9c950ywan} 164233d2500723e5594f3e7c70896ffeeef32b9c950ywan 165233d2500723e5594f3e7c70896ffeeef32b9c950ywanchar * h_strdup(const char * str) 166233d2500723e5594f3e7c70896ffeeef32b9c950ywan{ 167233d2500723e5594f3e7c70896ffeeef32b9c950ywan size_t len = strlen(str); 168233d2500723e5594f3e7c70896ffeeef32b9c950ywan char * ptr = halloc(0, len + 1); 169233d2500723e5594f3e7c70896ffeeef32b9c950ywan return ptr ? (ptr[len] = 0, memcpy(ptr, str, len)) : NULL; 170233d2500723e5594f3e7c70896ffeeef32b9c950ywan} 171233d2500723e5594f3e7c70896ffeeef32b9c950ywan 172233d2500723e5594f3e7c70896ffeeef32b9c950ywan/* 173233d2500723e5594f3e7c70896ffeeef32b9c950ywan * static stuff 174233d2500723e5594f3e7c70896ffeeef32b9c950ywan */ 175233d2500723e5594f3e7c70896ffeeef32b9c950ywanstatic void _set_allocator(void) 176233d2500723e5594f3e7c70896ffeeef32b9c950ywan{ 177233d2500723e5594f3e7c70896ffeeef32b9c950ywan void * p; 178233d2500723e5594f3e7c70896ffeeef32b9c950ywan assert(! allocator); 179233d2500723e5594f3e7c70896ffeeef32b9c950ywan 180233d2500723e5594f3e7c70896ffeeef32b9c950ywan /* 181233d2500723e5594f3e7c70896ffeeef32b9c950ywan * the purpose of the test below is to check the behaviour 182233d2500723e5594f3e7c70896ffeeef32b9c950ywan * of realloc(ptr, 0), which is defined in the standard 183233d2500723e5594f3e7c70896ffeeef32b9c950ywan * as an implementation-specific. if it returns zero, 184233d2500723e5594f3e7c70896ffeeef32b9c950ywan * then it's equivalent to free(). it can however return 185233d2500723e5594f3e7c70896ffeeef32b9c950ywan * non-zero, in which case it cannot be used for freeing 186233d2500723e5594f3e7c70896ffeeef32b9c950ywan * memory blocks and we'll need to supply our own version 187233d2500723e5594f3e7c70896ffeeef32b9c950ywan * 188233d2500723e5594f3e7c70896ffeeef32b9c950ywan * Thanks to Stan Tobias for pointing this tricky part out. 189233d2500723e5594f3e7c70896ffeeef32b9c950ywan */ 190233d2500723e5594f3e7c70896ffeeef32b9c950ywan allocator = realloc; 191233d2500723e5594f3e7c70896ffeeef32b9c950ywan if (! (p = malloc(1))) 192233d2500723e5594f3e7c70896ffeeef32b9c950ywan /* hmm */ 193233d2500723e5594f3e7c70896ffeeef32b9c950ywan return; 194233d2500723e5594f3e7c70896ffeeef32b9c950ywan 195233d2500723e5594f3e7c70896ffeeef32b9c950ywan if ((p = realloc(p, 0))) 196233d2500723e5594f3e7c70896ffeeef32b9c950ywan { 197233d2500723e5594f3e7c70896ffeeef32b9c950ywan /* realloc cannot be used as free() */ 198233d2500723e5594f3e7c70896ffeeef32b9c950ywan allocator = _realloc; 199233d2500723e5594f3e7c70896ffeeef32b9c950ywan free(p); 200233d2500723e5594f3e7c70896ffeeef32b9c950ywan } 201233d2500723e5594f3e7c70896ffeeef32b9c950ywan} 202233d2500723e5594f3e7c70896ffeeef32b9c950ywan 203233d2500723e5594f3e7c70896ffeeef32b9c950ywanstatic void * _realloc(void * ptr, size_t n) 204233d2500723e5594f3e7c70896ffeeef32b9c950ywan{ 205233d2500723e5594f3e7c70896ffeeef32b9c950ywan /* 206233d2500723e5594f3e7c70896ffeeef32b9c950ywan * free'ing realloc() 207233d2500723e5594f3e7c70896ffeeef32b9c950ywan */ 208233d2500723e5594f3e7c70896ffeeef32b9c950ywan if (n) 209233d2500723e5594f3e7c70896ffeeef32b9c950ywan return realloc(ptr, n); 210233d2500723e5594f3e7c70896ffeeef32b9c950ywan free(ptr); 211233d2500723e5594f3e7c70896ffeeef32b9c950ywan return NULL; 212233d2500723e5594f3e7c70896ffeeef32b9c950ywan} 213233d2500723e5594f3e7c70896ffeeef32b9c950ywan 214233d2500723e5594f3e7c70896ffeeef32b9c950ywanstatic int _relate(hblock_t * b, hblock_t * p) 215233d2500723e5594f3e7c70896ffeeef32b9c950ywan{ 216233d2500723e5594f3e7c70896ffeeef32b9c950ywan hlist_item_t * i; 217233d2500723e5594f3e7c70896ffeeef32b9c950ywan 218233d2500723e5594f3e7c70896ffeeef32b9c950ywan if (!b || !p) 219233d2500723e5594f3e7c70896ffeeef32b9c950ywan return 0; 220233d2500723e5594f3e7c70896ffeeef32b9c950ywan 221233d2500723e5594f3e7c70896ffeeef32b9c950ywan /* 222233d2500723e5594f3e7c70896ffeeef32b9c950ywan * since there is no 'parent' pointer, which would've allowed 223233d2500723e5594f3e7c70896ffeeef32b9c950ywan * O(log(n)) upward traversal, the check must use O(n) downward 224233d2500723e5594f3e7c70896ffeeef32b9c950ywan * iteration of the entire hierarchy; and this can be VERY SLOW 225233d2500723e5594f3e7c70896ffeeef32b9c950ywan */ 226233d2500723e5594f3e7c70896ffeeef32b9c950ywan hlist_for_each(i, &p->children) 227233d2500723e5594f3e7c70896ffeeef32b9c950ywan { 228233d2500723e5594f3e7c70896ffeeef32b9c950ywan hblock_t * q = structof(i, hblock_t, siblings); 229233d2500723e5594f3e7c70896ffeeef32b9c950ywan if (q == b || _relate(b, q)) 230233d2500723e5594f3e7c70896ffeeef32b9c950ywan return 1; 231233d2500723e5594f3e7c70896ffeeef32b9c950ywan } 232233d2500723e5594f3e7c70896ffeeef32b9c950ywan return 0; 233233d2500723e5594f3e7c70896ffeeef32b9c950ywan} 234233d2500723e5594f3e7c70896ffeeef32b9c950ywan 235233d2500723e5594f3e7c70896ffeeef32b9c950ywanstatic void _free_children(hblock_t * p) 236233d2500723e5594f3e7c70896ffeeef32b9c950ywan{ 237233d2500723e5594f3e7c70896ffeeef32b9c950ywan hlist_item_t * i, * tmp; 238233d2500723e5594f3e7c70896ffeeef32b9c950ywan 239233d2500723e5594f3e7c70896ffeeef32b9c950ywan#ifndef NDEBUG 240233d2500723e5594f3e7c70896ffeeef32b9c950ywan /* 241233d2500723e5594f3e7c70896ffeeef32b9c950ywan * this catches loops in hierarchy with almost zero 242233d2500723e5594f3e7c70896ffeeef32b9c950ywan * overhead (compared to _relate() running time) 243233d2500723e5594f3e7c70896ffeeef32b9c950ywan */ 244233d2500723e5594f3e7c70896ffeeef32b9c950ywan assert(p && p->magic == HH_MAGIC); 245233d2500723e5594f3e7c70896ffeeef32b9c950ywan p->magic = 0; 246233d2500723e5594f3e7c70896ffeeef32b9c950ywan#endif 247233d2500723e5594f3e7c70896ffeeef32b9c950ywan hlist_for_each_safe(i, tmp, &p->children) 248233d2500723e5594f3e7c70896ffeeef32b9c950ywan { 249233d2500723e5594f3e7c70896ffeeef32b9c950ywan hblock_t * q = structof(i, hblock_t, siblings); 250233d2500723e5594f3e7c70896ffeeef32b9c950ywan _free_children(q); 251233d2500723e5594f3e7c70896ffeeef32b9c950ywan allocator(q, 0); 252233d2500723e5594f3e7c70896ffeeef32b9c950ywan } 253233d2500723e5594f3e7c70896ffeeef32b9c950ywan} 254233d2500723e5594f3e7c70896ffeeef32b9c950ywan 255