1346ee2f7978bf2ab1ead4982e56870da276fc44bflorian/* -*- mode: C; c-basic-offset: 3; -*- */ 2346ee2f7978bf2ab1ead4982e56870da276fc44bflorian 3346ee2f7978bf2ab1ead4982e56870da276fc44bflorian/*--------------------------------------------------------------------*/ 4346ee2f7978bf2ab1ead4982e56870da276fc44bflorian/*--- Segment name management aspacemgr-segnames.c ---*/ 5346ee2f7978bf2ab1ead4982e56870da276fc44bflorian/*--------------------------------------------------------------------*/ 6346ee2f7978bf2ab1ead4982e56870da276fc44bflorian 7346ee2f7978bf2ab1ead4982e56870da276fc44bflorian/* 8346ee2f7978bf2ab1ead4982e56870da276fc44bflorian This file is part of Valgrind, a dynamic binary instrumentation 9346ee2f7978bf2ab1ead4982e56870da276fc44bflorian framework. 10346ee2f7978bf2ab1ead4982e56870da276fc44bflorian 11346ee2f7978bf2ab1ead4982e56870da276fc44bflorian Copyright (C) 2015-2015 Florian Krohm 12346ee2f7978bf2ab1ead4982e56870da276fc44bflorian 13346ee2f7978bf2ab1ead4982e56870da276fc44bflorian This program is free software; you can redistribute it and/or 14346ee2f7978bf2ab1ead4982e56870da276fc44bflorian modify it under the terms of the GNU General Public License as 15346ee2f7978bf2ab1ead4982e56870da276fc44bflorian published by the Free Software Foundation; either version 2 of the 16346ee2f7978bf2ab1ead4982e56870da276fc44bflorian License, or (at your option) any later version. 17346ee2f7978bf2ab1ead4982e56870da276fc44bflorian 18346ee2f7978bf2ab1ead4982e56870da276fc44bflorian This program is distributed in the hope that it will be useful, but 19346ee2f7978bf2ab1ead4982e56870da276fc44bflorian WITHOUT ANY WARRANTY; without even the implied warranty of 20346ee2f7978bf2ab1ead4982e56870da276fc44bflorian MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 21346ee2f7978bf2ab1ead4982e56870da276fc44bflorian General Public License for more details. 22346ee2f7978bf2ab1ead4982e56870da276fc44bflorian 23346ee2f7978bf2ab1ead4982e56870da276fc44bflorian You should have received a copy of the GNU General Public License 24346ee2f7978bf2ab1ead4982e56870da276fc44bflorian along with this program; if not, write to the Free Software 25346ee2f7978bf2ab1ead4982e56870da276fc44bflorian Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 26346ee2f7978bf2ab1ead4982e56870da276fc44bflorian 02111-1307, USA. 27346ee2f7978bf2ab1ead4982e56870da276fc44bflorian 28346ee2f7978bf2ab1ead4982e56870da276fc44bflorian The GNU General Public License is contained in the file COPYING. 29346ee2f7978bf2ab1ead4982e56870da276fc44bflorian*/ 30346ee2f7978bf2ab1ead4982e56870da276fc44bflorian 31346ee2f7978bf2ab1ead4982e56870da276fc44bflorian/* Segment names are stored in a string table. 32346ee2f7978bf2ab1ead4982e56870da276fc44bflorian 33346ee2f7978bf2ab1ead4982e56870da276fc44bflorian The string table is organised into slots of varying length. Slots are 34346ee2f7978bf2ab1ead4982e56870da276fc44bflorian adjacent and there are no holes between slots. 35346ee2f7978bf2ab1ead4982e56870da276fc44bflorian A slot consists of two parts: 36346ee2f7978bf2ab1ead4982e56870da276fc44bflorian 37346ee2f7978bf2ab1ead4982e56870da276fc44bflorian (1) a fixed size overhead of length 4 bytes 38346ee2f7978bf2ab1ead4982e56870da276fc44bflorian (2) a variable size payload of up to 65535 bytes 39346ee2f7978bf2ab1ead4982e56870da276fc44bflorian 40346ee2f7978bf2ab1ead4982e56870da276fc44bflorian The segment name is stored in the payload area. Therefore: 41346ee2f7978bf2ab1ead4982e56870da276fc44bflorian a segment name cannot be longer than 65535 bytes including the '\0' 42346ee2f7978bf2ab1ead4982e56870da276fc44bflorian terminator. This looks like a reasonable limitation. 43346ee2f7978bf2ab1ead4982e56870da276fc44bflorian 44346ee2f7978bf2ab1ead4982e56870da276fc44bflorian Overall slot layout: 45346ee2f7978bf2ab1ead4982e56870da276fc44bflorian 46346ee2f7978bf2ab1ead4982e56870da276fc44bflorian | 4 bytes | max 65535 bytes | 47346ee2f7978bf2ab1ead4982e56870da276fc44bflorian +-----------------------------+-------------------------+ 48346ee2f7978bf2ab1ead4982e56870da276fc44bflorian | overhead | payload | 49346ee2f7978bf2ab1ead4982e56870da276fc44bflorian +-----------------------------+-------------------------+ 50346ee2f7978bf2ab1ead4982e56870da276fc44bflorian ^ ^ 51346ee2f7978bf2ab1ead4982e56870da276fc44bflorian | | 52346ee2f7978bf2ab1ead4982e56870da276fc44bflorian -4 +----- seg->fnIdx 53346ee2f7978bf2ab1ead4982e56870da276fc44bflorian 54346ee2f7978bf2ab1ead4982e56870da276fc44bflorian Each slot is uniquely identified by an index which points to the first 55346ee2f7978bf2ab1ead4982e56870da276fc44bflorian byte of the payload area. It is this value that is stored in seg->fnIdx. 56346ee2f7978bf2ab1ead4982e56870da276fc44bflorian Note, that this value is at least 4. 57346ee2f7978bf2ab1ead4982e56870da276fc44bflorian 58346ee2f7978bf2ab1ead4982e56870da276fc44bflorian A slot either holds a string or it is free. The status of a slot is 59346ee2f7978bf2ab1ead4982e56870da276fc44bflorian identified by the leftmost bit in the overhead field, the so called F-bit. 60346ee2f7978bf2ab1ead4982e56870da276fc44bflorian F-bit == 1 means that slot is free; otherwise it is occupied and holds a 61346ee2f7978bf2ab1ead4982e56870da276fc44bflorian string. 62346ee2f7978bf2ab1ead4982e56870da276fc44bflorian 63346ee2f7978bf2ab1ead4982e56870da276fc44bflorian Slot containing a string (segment name): 64346ee2f7978bf2ab1ead4982e56870da276fc44bflorian 65346ee2f7978bf2ab1ead4982e56870da276fc44bflorian bits | 1 | 15 | 16 | 66346ee2f7978bf2ab1ead4982e56870da276fc44bflorian +---+--------------+----------+-------------------------+ 67346ee2f7978bf2ab1ead4982e56870da276fc44bflorian | 0 | refcount | slotsize | the string including \0 | 68346ee2f7978bf2ab1ead4982e56870da276fc44bflorian +---+--------------+----------+-------------------------+ 69346ee2f7978bf2ab1ead4982e56870da276fc44bflorian ^ ^ ^ 70346ee2f7978bf2ab1ead4982e56870da276fc44bflorian | | | 71346ee2f7978bf2ab1ead4982e56870da276fc44bflorian -4 -2 +----- seg->fnIdx 72346ee2f7978bf2ab1ead4982e56870da276fc44bflorian 73346ee2f7978bf2ab1ead4982e56870da276fc44bflorian Segment names are reference counted. 15 bits are available which allows 74346ee2f7978bf2ab1ead4982e56870da276fc44bflorian for up to 32767 references. If the string is referenced more than 32767 75346ee2f7978bf2ab1ead4982e56870da276fc44bflorian times, the reference count will be frozen and the slot can never 76346ee2f7978bf2ab1ead4982e56870da276fc44bflorian become free. I'm not unduly concerned. 77346ee2f7978bf2ab1ead4982e56870da276fc44bflorian Two bytes are reserved to hold the size of the slot. Well, it's actually 78346ee2f7978bf2ab1ead4982e56870da276fc44bflorian the size of the payload aread (i.e. the size of the slot minus the 79346ee2f7978bf2ab1ead4982e56870da276fc44bflorian overhead). Ah well -- the name sticks. 80346ee2f7978bf2ab1ead4982e56870da276fc44bflorian With two bytes to store the size, the payload area can be at most 65535 81346ee2f7978bf2ab1ead4982e56870da276fc44bflorian bytes large. 82346ee2f7978bf2ab1ead4982e56870da276fc44bflorian 83346ee2f7978bf2ab1ead4982e56870da276fc44bflorian A free slot looks like this: 84346ee2f7978bf2ab1ead4982e56870da276fc44bflorian 85346ee2f7978bf2ab1ead4982e56870da276fc44bflorian bits | 1 | 31 | 16 | 86346ee2f7978bf2ab1ead4982e56870da276fc44bflorian +---+-------------------------+----------+--------------+ 87346ee2f7978bf2ab1ead4982e56870da276fc44bflorian | 1 | index of next free slot | slotsize | .. unused .. | 88346ee2f7978bf2ab1ead4982e56870da276fc44bflorian +---+-------------------------+----------+--------------+ 89346ee2f7978bf2ab1ead4982e56870da276fc44bflorian ^ ^ 90346ee2f7978bf2ab1ead4982e56870da276fc44bflorian | | 91346ee2f7978bf2ab1ead4982e56870da276fc44bflorian -4 +----- seg->fnIdx 92346ee2f7978bf2ab1ead4982e56870da276fc44bflorian 93346ee2f7978bf2ab1ead4982e56870da276fc44bflorian Free slots are chained together in a singly linked list. An index of 94346ee2f7978bf2ab1ead4982e56870da276fc44bflorian zero indicates the end of the chain. Note that zero cannot conflict 95346ee2f7978bf2ab1ead4982e56870da276fc44bflorian with an index into the string table as the minumum index is at least 96346ee2f7978bf2ab1ead4982e56870da276fc44bflorian four (see above). 97346ee2f7978bf2ab1ead4982e56870da276fc44bflorian 98346ee2f7978bf2ab1ead4982e56870da276fc44bflorian The typical way to traverse the segment names is: 99346ee2f7978bf2ab1ead4982e56870da276fc44bflorian 100346ee2f7978bf2ab1ead4982e56870da276fc44bflorian for (ix = overhead; (size = get_slotsize(ix)) != 0; ix += size + overhead) { 101346ee2f7978bf2ab1ead4982e56870da276fc44bflorian if (is_freeslot(ix)) 102346ee2f7978bf2ab1ead4982e56870da276fc44bflorian do this 103346ee2f7978bf2ab1ead4982e56870da276fc44bflorian else 104346ee2f7978bf2ab1ead4982e56870da276fc44bflorian do that 105346ee2f7978bf2ab1ead4982e56870da276fc44bflorian } 106346ee2f7978bf2ab1ead4982e56870da276fc44bflorian 107346ee2f7978bf2ab1ead4982e56870da276fc44bflorian Important detail: there is a sentinel at the end of the list, namely a 108346ee2f7978bf2ab1ead4982e56870da276fc44bflorian slot with a zero-sized payload area. 109346ee2f7978bf2ab1ead4982e56870da276fc44bflorian 110346ee2f7978bf2ab1ead4982e56870da276fc44bflorian Whenever a new segment name needs to be stashed away, the list of free 111346ee2f7978bf2ab1ead4982e56870da276fc44bflorian slots is traversed and the first slot which is large enough is being taken 112346ee2f7978bf2ab1ead4982e56870da276fc44bflorian (first fit). There will be no splitting of slots, as that complicates 113346ee2f7978bf2ab1ead4982e56870da276fc44bflorian matters and without slot coalescing would lead to memory fragmentation. 114346ee2f7978bf2ab1ead4982e56870da276fc44bflorian So we leave it as is until a use case comes up that needs something better. 115346ee2f7978bf2ab1ead4982e56870da276fc44bflorian*/ 116346ee2f7978bf2ab1ead4982e56870da276fc44bflorian 117346ee2f7978bf2ab1ead4982e56870da276fc44bflorian#include "pub_core_basics.h" // types 118346ee2f7978bf2ab1ead4982e56870da276fc44bflorian#include "priv_aspacemgr.h" 119346ee2f7978bf2ab1ead4982e56870da276fc44bflorian 120346ee2f7978bf2ab1ead4982e56870da276fc44bflorian// A few constants. 121346ee2f7978bf2ab1ead4982e56870da276fc44bflorianenum { 122346ee2f7978bf2ab1ead4982e56870da276fc44bflorian refcount_size = sizeof(UShort), 123346ee2f7978bf2ab1ead4982e56870da276fc44bflorian slotsize_size = sizeof(UShort), 124346ee2f7978bf2ab1ead4982e56870da276fc44bflorian overhead = refcount_size + slotsize_size, 125346ee2f7978bf2ab1ead4982e56870da276fc44bflorian max_refcount = 0x7fff, // 2 bytes - F-bit 126346ee2f7978bf2ab1ead4982e56870da276fc44bflorian max_slotsize = 0xffff, // 2 bytes 127346ee2f7978bf2ab1ead4982e56870da276fc44bflorian max_slotindex = 0x7fffffff, // 4 bytes - F-bit 128346ee2f7978bf2ab1ead4982e56870da276fc44bflorian fbit_mask = 0x80, 129346ee2f7978bf2ab1ead4982e56870da276fc44bflorian end_of_chain = 0 130346ee2f7978bf2ab1ead4982e56870da276fc44bflorian}; 131346ee2f7978bf2ab1ead4982e56870da276fc44bflorian 132346ee2f7978bf2ab1ead4982e56870da276fc44bflorian/* The old segname implementation allowed for 1000 names on Android and 133346ee2f7978bf2ab1ead4982e56870da276fc44bflorian 6000 names on other platforms. Each name was allowed to be 1000 characters 134346ee2f7978bf2ab1ead4982e56870da276fc44bflorian long. That was very wasteful. */ 135346ee2f7978bf2ab1ead4982e56870da276fc44bflorian#define VG_TABLE_SIZE 1000000 136346ee2f7978bf2ab1ead4982e56870da276fc44bflorian 137346ee2f7978bf2ab1ead4982e56870da276fc44bflorian/* String table for segment names */ 138346ee2f7978bf2ab1ead4982e56870da276fc44bflorian 139346ee2f7978bf2ab1ead4982e56870da276fc44bflorianstatic HChar segnames[VG_TABLE_SIZE]; /* her majesty, the string table */ 140346ee2f7978bf2ab1ead4982e56870da276fc44bflorianstatic SizeT segnames_used = 0; /* number of bytes used */ 141346ee2f7978bf2ab1ead4982e56870da276fc44bflorianstatic UInt num_segnames = 0; /* number of names in string table */ 142346ee2f7978bf2ab1ead4982e56870da276fc44bflorianstatic UInt num_slots = 0; /* number of slots in string table */ 143346ee2f7978bf2ab1ead4982e56870da276fc44bflorianstatic UInt freeslot_chain = end_of_chain; 144346ee2f7978bf2ab1ead4982e56870da276fc44bflorian 145346ee2f7978bf2ab1ead4982e56870da276fc44bflorianstatic Bool 146346ee2f7978bf2ab1ead4982e56870da276fc44bflorianis_freeslot(UInt ix) 147346ee2f7978bf2ab1ead4982e56870da276fc44bflorian{ 148346ee2f7978bf2ab1ead4982e56870da276fc44bflorian aspacem_assert(ix >= overhead && ix <= segnames_used); 149346ee2f7978bf2ab1ead4982e56870da276fc44bflorian return (segnames[ix - 4] & fbit_mask) != 0; 150346ee2f7978bf2ab1ead4982e56870da276fc44bflorian} 151346ee2f7978bf2ab1ead4982e56870da276fc44bflorian 152346ee2f7978bf2ab1ead4982e56870da276fc44bflorianstatic void 153346ee2f7978bf2ab1ead4982e56870da276fc44bflorianput_slotindex(UInt ix, UInt slotindex) 154346ee2f7978bf2ab1ead4982e56870da276fc44bflorian{ 155346ee2f7978bf2ab1ead4982e56870da276fc44bflorian aspacem_assert(ix >= overhead && ix <= segnames_used); 156346ee2f7978bf2ab1ead4982e56870da276fc44bflorian if (slotindex != 0) 157346ee2f7978bf2ab1ead4982e56870da276fc44bflorian aspacem_assert(slotindex >= overhead && slotindex <= segnames_used); 158346ee2f7978bf2ab1ead4982e56870da276fc44bflorian 159346ee2f7978bf2ab1ead4982e56870da276fc44bflorian slotindex |= fbit_mask << 24; 160346ee2f7978bf2ab1ead4982e56870da276fc44bflorian segnames[ix - 1] = slotindex & 0xFF; slotindex >>= 8; 161346ee2f7978bf2ab1ead4982e56870da276fc44bflorian segnames[ix - 2] = slotindex & 0xFF; slotindex >>= 8; 162346ee2f7978bf2ab1ead4982e56870da276fc44bflorian segnames[ix - 3] = slotindex & 0xFF; slotindex >>= 8; 163346ee2f7978bf2ab1ead4982e56870da276fc44bflorian segnames[ix - 4] = slotindex & 0xFF; 164346ee2f7978bf2ab1ead4982e56870da276fc44bflorian} 165346ee2f7978bf2ab1ead4982e56870da276fc44bflorian 166346ee2f7978bf2ab1ead4982e56870da276fc44bflorianstatic UInt 167346ee2f7978bf2ab1ead4982e56870da276fc44bflorianget_slotindex(UInt ix) 168346ee2f7978bf2ab1ead4982e56870da276fc44bflorian{ 169346ee2f7978bf2ab1ead4982e56870da276fc44bflorian aspacem_assert(ix >= overhead && ix <= segnames_used); 170346ee2f7978bf2ab1ead4982e56870da276fc44bflorian aspacem_assert(is_freeslot(ix)); 171346ee2f7978bf2ab1ead4982e56870da276fc44bflorian 172346ee2f7978bf2ab1ead4982e56870da276fc44bflorian // Avoid unexpected sign extension 173346ee2f7978bf2ab1ead4982e56870da276fc44bflorian const UChar *unames = (const UChar *)segnames; 174346ee2f7978bf2ab1ead4982e56870da276fc44bflorian 175346ee2f7978bf2ab1ead4982e56870da276fc44bflorian UInt slotindex = 0; 176346ee2f7978bf2ab1ead4982e56870da276fc44bflorian slotindex |= unames[ix - 4]; slotindex <<= 8; 177346ee2f7978bf2ab1ead4982e56870da276fc44bflorian slotindex |= unames[ix - 3]; slotindex <<= 8; 178346ee2f7978bf2ab1ead4982e56870da276fc44bflorian slotindex |= unames[ix - 2]; slotindex <<= 8; 179346ee2f7978bf2ab1ead4982e56870da276fc44bflorian slotindex |= unames[ix - 1]; 180346ee2f7978bf2ab1ead4982e56870da276fc44bflorian 181346ee2f7978bf2ab1ead4982e56870da276fc44bflorian return slotindex & max_slotindex; // removes the F-bit 182346ee2f7978bf2ab1ead4982e56870da276fc44bflorian} 183346ee2f7978bf2ab1ead4982e56870da276fc44bflorian 184346ee2f7978bf2ab1ead4982e56870da276fc44bflorianstatic void 185346ee2f7978bf2ab1ead4982e56870da276fc44bflorianput_slotsize(UInt ix, UInt size) 186346ee2f7978bf2ab1ead4982e56870da276fc44bflorian{ 187346ee2f7978bf2ab1ead4982e56870da276fc44bflorian aspacem_assert(ix >= overhead && ix <= segnames_used); 188346ee2f7978bf2ab1ead4982e56870da276fc44bflorian aspacem_assert(size <= max_slotsize); 189346ee2f7978bf2ab1ead4982e56870da276fc44bflorian segnames[ix - 1] = size & 0xff; 190346ee2f7978bf2ab1ead4982e56870da276fc44bflorian segnames[ix - 2] = size >> 8; 191346ee2f7978bf2ab1ead4982e56870da276fc44bflorian} 192346ee2f7978bf2ab1ead4982e56870da276fc44bflorian 193346ee2f7978bf2ab1ead4982e56870da276fc44bflorianstatic UInt 194346ee2f7978bf2ab1ead4982e56870da276fc44bflorianget_slotsize(UInt ix) 195346ee2f7978bf2ab1ead4982e56870da276fc44bflorian{ 196346ee2f7978bf2ab1ead4982e56870da276fc44bflorian aspacem_assert(ix >= overhead && ix <= segnames_used); 197346ee2f7978bf2ab1ead4982e56870da276fc44bflorian 198346ee2f7978bf2ab1ead4982e56870da276fc44bflorian // Avoid unexpected sign extension 199346ee2f7978bf2ab1ead4982e56870da276fc44bflorian const UChar *unames = (const UChar *)segnames; 200346ee2f7978bf2ab1ead4982e56870da276fc44bflorian if (is_freeslot(ix)) 201346ee2f7978bf2ab1ead4982e56870da276fc44bflorian return (unames[ix] << 8) | unames[ix+1]; 202346ee2f7978bf2ab1ead4982e56870da276fc44bflorian else 203346ee2f7978bf2ab1ead4982e56870da276fc44bflorian return (unames[ix - 2] << 8) | unames[ix - 1]; 204346ee2f7978bf2ab1ead4982e56870da276fc44bflorian} 205346ee2f7978bf2ab1ead4982e56870da276fc44bflorian 206346ee2f7978bf2ab1ead4982e56870da276fc44bflorianstatic void 207346ee2f7978bf2ab1ead4982e56870da276fc44bflorianput_refcount(UInt ix, UInt rc) 208346ee2f7978bf2ab1ead4982e56870da276fc44bflorian{ 209346ee2f7978bf2ab1ead4982e56870da276fc44bflorian aspacem_assert(ix >= overhead && ix <= segnames_used); 210346ee2f7978bf2ab1ead4982e56870da276fc44bflorian aspacem_assert(rc <= max_refcount); 211346ee2f7978bf2ab1ead4982e56870da276fc44bflorian // rc <= max_refcount ensures that the F-bit is zero 212346ee2f7978bf2ab1ead4982e56870da276fc44bflorian segnames[ix - 3] = rc & 0xff; 213346ee2f7978bf2ab1ead4982e56870da276fc44bflorian segnames[ix - 4] = rc >> 8; 214346ee2f7978bf2ab1ead4982e56870da276fc44bflorian} 215346ee2f7978bf2ab1ead4982e56870da276fc44bflorian 216346ee2f7978bf2ab1ead4982e56870da276fc44bflorianstatic UInt 217346ee2f7978bf2ab1ead4982e56870da276fc44bflorianget_refcount(UInt ix) 218346ee2f7978bf2ab1ead4982e56870da276fc44bflorian{ 219346ee2f7978bf2ab1ead4982e56870da276fc44bflorian aspacem_assert(ix >= overhead && ix <= segnames_used); 220346ee2f7978bf2ab1ead4982e56870da276fc44bflorian // must not be a free slot 221346ee2f7978bf2ab1ead4982e56870da276fc44bflorian aspacem_assert(! is_freeslot(ix)); 222346ee2f7978bf2ab1ead4982e56870da276fc44bflorian 223346ee2f7978bf2ab1ead4982e56870da276fc44bflorian // Avoid unexpected sign extension 224346ee2f7978bf2ab1ead4982e56870da276fc44bflorian const UChar *unames = (const UChar *)segnames; 225346ee2f7978bf2ab1ead4982e56870da276fc44bflorian return (unames[ix - 4] << 8) | unames[ix - 3]; 226346ee2f7978bf2ab1ead4982e56870da276fc44bflorian} 227346ee2f7978bf2ab1ead4982e56870da276fc44bflorian 228346ee2f7978bf2ab1ead4982e56870da276fc44bflorianstatic void 229346ee2f7978bf2ab1ead4982e56870da276fc44bflorianinc_refcount(UInt ix) 230346ee2f7978bf2ab1ead4982e56870da276fc44bflorian{ 231346ee2f7978bf2ab1ead4982e56870da276fc44bflorian aspacem_assert(ix >= overhead && ix <= segnames_used); 232346ee2f7978bf2ab1ead4982e56870da276fc44bflorian UInt rc = get_refcount(ix); 233346ee2f7978bf2ab1ead4982e56870da276fc44bflorian if (rc != max_refcount) 234346ee2f7978bf2ab1ead4982e56870da276fc44bflorian put_refcount(ix, rc + 1); 235346ee2f7978bf2ab1ead4982e56870da276fc44bflorian} 236346ee2f7978bf2ab1ead4982e56870da276fc44bflorian 237346ee2f7978bf2ab1ead4982e56870da276fc44bflorianstatic void 238346ee2f7978bf2ab1ead4982e56870da276fc44bfloriandec_refcount(UInt ix) 239346ee2f7978bf2ab1ead4982e56870da276fc44bflorian{ 240346ee2f7978bf2ab1ead4982e56870da276fc44bflorian aspacem_assert(ix >= overhead && ix <= segnames_used); 241346ee2f7978bf2ab1ead4982e56870da276fc44bflorian UInt rc = get_refcount(ix); 242346ee2f7978bf2ab1ead4982e56870da276fc44bflorian aspacem_assert(rc > 0); 243346ee2f7978bf2ab1ead4982e56870da276fc44bflorian if (rc != max_refcount) { 244346ee2f7978bf2ab1ead4982e56870da276fc44bflorian --rc; 245346ee2f7978bf2ab1ead4982e56870da276fc44bflorian if (rc != 0) { 246346ee2f7978bf2ab1ead4982e56870da276fc44bflorian put_refcount(ix, rc); 247346ee2f7978bf2ab1ead4982e56870da276fc44bflorian } else { 248346ee2f7978bf2ab1ead4982e56870da276fc44bflorian UInt size = get_slotsize(ix); 249346ee2f7978bf2ab1ead4982e56870da276fc44bflorian /* Chain this slot in the freelist */ 250346ee2f7978bf2ab1ead4982e56870da276fc44bflorian put_slotindex(ix, freeslot_chain); 251346ee2f7978bf2ab1ead4982e56870da276fc44bflorian get_slotindex(ix); 252346ee2f7978bf2ab1ead4982e56870da276fc44bflorian put_slotsize(ix + slotsize_size, size); 253346ee2f7978bf2ab1ead4982e56870da276fc44bflorian get_slotindex(ix); 254346ee2f7978bf2ab1ead4982e56870da276fc44bflorian freeslot_chain = ix; 255346ee2f7978bf2ab1ead4982e56870da276fc44bflorian --num_segnames; 256346ee2f7978bf2ab1ead4982e56870da276fc44bflorian if (0) VG_(am_show_nsegments)(0, "AFTER DECREASE rc -> 0"); 257346ee2f7978bf2ab1ead4982e56870da276fc44bflorian } 258346ee2f7978bf2ab1ead4982e56870da276fc44bflorian } 259346ee2f7978bf2ab1ead4982e56870da276fc44bflorian} 260346ee2f7978bf2ab1ead4982e56870da276fc44bflorian 261346ee2f7978bf2ab1ead4982e56870da276fc44bflorianstatic void 262346ee2f7978bf2ab1ead4982e56870da276fc44bflorianput_sentinel(UInt ix) 263346ee2f7978bf2ab1ead4982e56870da276fc44bflorian{ 264346ee2f7978bf2ab1ead4982e56870da276fc44bflorian aspacem_assert(ix >= overhead && ix <= segnames_used); 265346ee2f7978bf2ab1ead4982e56870da276fc44bflorian 266346ee2f7978bf2ab1ead4982e56870da276fc44bflorian put_refcount(ix, 0); 267346ee2f7978bf2ab1ead4982e56870da276fc44bflorian put_slotsize(ix, 0); 268346ee2f7978bf2ab1ead4982e56870da276fc44bflorian} 269346ee2f7978bf2ab1ead4982e56870da276fc44bflorian 270346ee2f7978bf2ab1ead4982e56870da276fc44bflorian 271346ee2f7978bf2ab1ead4982e56870da276fc44bflorian/* Searches the string table to find an index for the given name. 272346ee2f7978bf2ab1ead4982e56870da276fc44bflorian If none is found, an index is allocated and the name stored. 273346ee2f7978bf2ab1ead4982e56870da276fc44bflorian If running ouf of memory, return -1. */ 274346ee2f7978bf2ab1ead4982e56870da276fc44bflorianInt 2754ecd48360351f666f008148c12a24cbda455c6b1florianML_(am_allocate_segname)(const HChar *name) 276346ee2f7978bf2ab1ead4982e56870da276fc44bflorian{ 277346ee2f7978bf2ab1ead4982e56870da276fc44bflorian UInt len, ix, size, next_freeslot; 278346ee2f7978bf2ab1ead4982e56870da276fc44bflorian 279346ee2f7978bf2ab1ead4982e56870da276fc44bflorian aspacem_assert(name); 280346ee2f7978bf2ab1ead4982e56870da276fc44bflorian 281346ee2f7978bf2ab1ead4982e56870da276fc44bflorian if (0) VG_(debugLog)(0, "aspacem", "allocate_segname %s\n", name); 282346ee2f7978bf2ab1ead4982e56870da276fc44bflorian 283346ee2f7978bf2ab1ead4982e56870da276fc44bflorian len = VG_(strlen)(name); 284346ee2f7978bf2ab1ead4982e56870da276fc44bflorian 285346ee2f7978bf2ab1ead4982e56870da276fc44bflorian /* First see if we already have the name. */ 286346ee2f7978bf2ab1ead4982e56870da276fc44bflorian for (ix = overhead; (size = get_slotsize(ix)) != 0; ix += size + overhead) { 287346ee2f7978bf2ab1ead4982e56870da276fc44bflorian if (is_freeslot(ix)) continue; 288346ee2f7978bf2ab1ead4982e56870da276fc44bflorian if (VG_(strcmp)(name, segnames + ix) == 0) { 289346ee2f7978bf2ab1ead4982e56870da276fc44bflorian inc_refcount(ix); 290346ee2f7978bf2ab1ead4982e56870da276fc44bflorian return ix; 291346ee2f7978bf2ab1ead4982e56870da276fc44bflorian } 292346ee2f7978bf2ab1ead4982e56870da276fc44bflorian } 293346ee2f7978bf2ab1ead4982e56870da276fc44bflorian 294346ee2f7978bf2ab1ead4982e56870da276fc44bflorian /* Is there a free slot in the string table from a previously "freed" 295346ee2f7978bf2ab1ead4982e56870da276fc44bflorian segment name ? */ 296346ee2f7978bf2ab1ead4982e56870da276fc44bflorian Int prev; 297346ee2f7978bf2ab1ead4982e56870da276fc44bflorian for (prev = -1, ix = freeslot_chain; ix != end_of_chain; 298346ee2f7978bf2ab1ead4982e56870da276fc44bflorian prev = ix, ix = next_freeslot) { 299346ee2f7978bf2ab1ead4982e56870da276fc44bflorian next_freeslot = get_slotindex(ix); // next in chain 300346ee2f7978bf2ab1ead4982e56870da276fc44bflorian size = get_slotsize(ix); 301346ee2f7978bf2ab1ead4982e56870da276fc44bflorian 302346ee2f7978bf2ab1ead4982e56870da276fc44bflorian if (size >= len + 1) { 303346ee2f7978bf2ab1ead4982e56870da276fc44bflorian /* Note, if the size of the slot is a lot larger than the length 304346ee2f7978bf2ab1ead4982e56870da276fc44bflorian of the string we're about to store in it, we could split the 305346ee2f7978bf2ab1ead4982e56870da276fc44bflorian slot into two. But that complicates matters and as we're not 306346ee2f7978bf2ab1ead4982e56870da276fc44bflorian doing any coalescing of adjacent free slots this could lead to 307346ee2f7978bf2ab1ead4982e56870da276fc44bflorian fragmentation. */ 308346ee2f7978bf2ab1ead4982e56870da276fc44bflorian if (prev == -1) 309346ee2f7978bf2ab1ead4982e56870da276fc44bflorian freeslot_chain = next_freeslot; 310346ee2f7978bf2ab1ead4982e56870da276fc44bflorian else 311346ee2f7978bf2ab1ead4982e56870da276fc44bflorian put_slotindex(prev, next_freeslot); 312346ee2f7978bf2ab1ead4982e56870da276fc44bflorian put_refcount(ix, 1); 313346ee2f7978bf2ab1ead4982e56870da276fc44bflorian put_slotsize(ix, size); 314346ee2f7978bf2ab1ead4982e56870da276fc44bflorian VG_(strcpy)(segnames + ix, name); 315346ee2f7978bf2ab1ead4982e56870da276fc44bflorian ++num_segnames; 316346ee2f7978bf2ab1ead4982e56870da276fc44bflorian return ix; 317346ee2f7978bf2ab1ead4982e56870da276fc44bflorian } 318346ee2f7978bf2ab1ead4982e56870da276fc44bflorian } 319346ee2f7978bf2ab1ead4982e56870da276fc44bflorian 320346ee2f7978bf2ab1ead4982e56870da276fc44bflorian /* We need to add a new name. */ 321346ee2f7978bf2ab1ead4982e56870da276fc44bflorian 322346ee2f7978bf2ab1ead4982e56870da276fc44bflorian /* Note, that we need at least two bytes in the payload. The reason is 323346ee2f7978bf2ab1ead4982e56870da276fc44bflorian that the payload area will be used to store the size of the slot when 324346ee2f7978bf2ab1ead4982e56870da276fc44bflorian the slot is on the freelist. */ 325346ee2f7978bf2ab1ead4982e56870da276fc44bflorian if (len == 0) len = 1; 326346ee2f7978bf2ab1ead4982e56870da276fc44bflorian 327346ee2f7978bf2ab1ead4982e56870da276fc44bflorian /* Is there enough room in the string table? The OVERHEAD is for the 328346ee2f7978bf2ab1ead4982e56870da276fc44bflorian sentinel following the payload of new slot. */ 329346ee2f7978bf2ab1ead4982e56870da276fc44bflorian SizeT need = len + 1 + overhead; 330346ee2f7978bf2ab1ead4982e56870da276fc44bflorian if (need > (sizeof segnames) - segnames_used) { 331346ee2f7978bf2ab1ead4982e56870da276fc44bflorian return -1; 332346ee2f7978bf2ab1ead4982e56870da276fc44bflorian } 333346ee2f7978bf2ab1ead4982e56870da276fc44bflorian 334346ee2f7978bf2ab1ead4982e56870da276fc44bflorian ++num_segnames; 335346ee2f7978bf2ab1ead4982e56870da276fc44bflorian ++num_slots; 336346ee2f7978bf2ab1ead4982e56870da276fc44bflorian 337346ee2f7978bf2ab1ead4982e56870da276fc44bflorian /* copy it in */ 338346ee2f7978bf2ab1ead4982e56870da276fc44bflorian ix = segnames_used; 339346ee2f7978bf2ab1ead4982e56870da276fc44bflorian put_refcount(ix, 1); 340346ee2f7978bf2ab1ead4982e56870da276fc44bflorian put_slotsize(ix, len + 1); 341346ee2f7978bf2ab1ead4982e56870da276fc44bflorian VG_(strcpy)(segnames + ix, name); 342346ee2f7978bf2ab1ead4982e56870da276fc44bflorian segnames_used += need; 343346ee2f7978bf2ab1ead4982e56870da276fc44bflorian 344346ee2f7978bf2ab1ead4982e56870da276fc44bflorian /* Add sentinel at end of segment name list */ 345346ee2f7978bf2ab1ead4982e56870da276fc44bflorian put_sentinel(segnames_used); 346346ee2f7978bf2ab1ead4982e56870da276fc44bflorian 347346ee2f7978bf2ab1ead4982e56870da276fc44bflorian return ix; 348346ee2f7978bf2ab1ead4982e56870da276fc44bflorian} 349346ee2f7978bf2ab1ead4982e56870da276fc44bflorian 350346ee2f7978bf2ab1ead4982e56870da276fc44bflorian/* Debugging output */ 351346ee2f7978bf2ab1ead4982e56870da276fc44bflorianvoid 3524ecd48360351f666f008148c12a24cbda455c6b1florianML_(am_show_segnames)(Int logLevel, const HChar *prefix) 353346ee2f7978bf2ab1ead4982e56870da276fc44bflorian{ 354346ee2f7978bf2ab1ead4982e56870da276fc44bflorian UInt size, ix, i; 355346ee2f7978bf2ab1ead4982e56870da276fc44bflorian 356346ee2f7978bf2ab1ead4982e56870da276fc44bflorian VG_(debugLog)(logLevel, "aspacem", "%u segment names in %u slots\n", 357346ee2f7978bf2ab1ead4982e56870da276fc44bflorian num_segnames, num_slots); 358346ee2f7978bf2ab1ead4982e56870da276fc44bflorian 359346ee2f7978bf2ab1ead4982e56870da276fc44bflorian if (freeslot_chain == end_of_chain) 360346ee2f7978bf2ab1ead4982e56870da276fc44bflorian VG_(debugLog)(logLevel, "aspacem", "freelist is empty\n"); 361346ee2f7978bf2ab1ead4982e56870da276fc44bflorian else 362346ee2f7978bf2ab1ead4982e56870da276fc44bflorian VG_(debugLog)(logLevel, "aspacem", "freelist begins at %u\n", 363346ee2f7978bf2ab1ead4982e56870da276fc44bflorian freeslot_chain); 364346ee2f7978bf2ab1ead4982e56870da276fc44bflorian for (i = 0, ix = overhead; (size = get_slotsize(ix)) != 0; 365346ee2f7978bf2ab1ead4982e56870da276fc44bflorian ix += size + overhead, ++i) { 366346ee2f7978bf2ab1ead4982e56870da276fc44bflorian if (is_freeslot(ix)) 367346ee2f7978bf2ab1ead4982e56870da276fc44bflorian VG_(debugLog)(logLevel, "aspacem", 368346ee2f7978bf2ab1ead4982e56870da276fc44bflorian "(%u,%u,0) [free slot: size=%u next=%u]\n", i, ix, 369346ee2f7978bf2ab1ead4982e56870da276fc44bflorian get_slotsize(ix), get_slotindex(ix)); 370346ee2f7978bf2ab1ead4982e56870da276fc44bflorian else 371346ee2f7978bf2ab1ead4982e56870da276fc44bflorian VG_(debugLog)(logLevel, "aspacem", 372346ee2f7978bf2ab1ead4982e56870da276fc44bflorian "(%u,%u,%u) %s\n", i, ix, get_refcount(ix), 373346ee2f7978bf2ab1ead4982e56870da276fc44bflorian segnames + ix); 374346ee2f7978bf2ab1ead4982e56870da276fc44bflorian } 375346ee2f7978bf2ab1ead4982e56870da276fc44bflorian} 376346ee2f7978bf2ab1ead4982e56870da276fc44bflorian 377346ee2f7978bf2ab1ead4982e56870da276fc44bflorian/* Returns a sequence number for the fnIdx position in segnames. 378346ee2f7978bf2ab1ead4982e56870da276fc44bflorian Used in aspacemgr debug output to associate a segment with 379346ee2f7978bf2ab1ead4982e56870da276fc44bflorian a segment name. */ 380346ee2f7978bf2ab1ead4982e56870da276fc44bflorianInt 3814ecd48360351f666f008148c12a24cbda455c6b1florianML_(am_segname_get_seqnr)(Int fnIdx) 382346ee2f7978bf2ab1ead4982e56870da276fc44bflorian{ 383346ee2f7978bf2ab1ead4982e56870da276fc44bflorian SizeT ix, size; 384346ee2f7978bf2ab1ead4982e56870da276fc44bflorian Int seqnr = -1; 385346ee2f7978bf2ab1ead4982e56870da276fc44bflorian 386346ee2f7978bf2ab1ead4982e56870da276fc44bflorian if (fnIdx == -1) return -1; // shortcut 387346ee2f7978bf2ab1ead4982e56870da276fc44bflorian 388346ee2f7978bf2ab1ead4982e56870da276fc44bflorian for (ix = overhead; (size = get_slotsize(ix)) != 0; ix += size + overhead) { 389346ee2f7978bf2ab1ead4982e56870da276fc44bflorian seqnr++; 390346ee2f7978bf2ab1ead4982e56870da276fc44bflorian if (ix == fnIdx) 391346ee2f7978bf2ab1ead4982e56870da276fc44bflorian return seqnr; 392346ee2f7978bf2ab1ead4982e56870da276fc44bflorian } 393346ee2f7978bf2ab1ead4982e56870da276fc44bflorian 394346ee2f7978bf2ab1ead4982e56870da276fc44bflorian // We should always find the given index; something's busted 395346ee2f7978bf2ab1ead4982e56870da276fc44bflorian aspacem_assert(0); 396346ee2f7978bf2ab1ead4982e56870da276fc44bflorian return -1; 397346ee2f7978bf2ab1ead4982e56870da276fc44bflorian} 398346ee2f7978bf2ab1ead4982e56870da276fc44bflorian 399346ee2f7978bf2ab1ead4982e56870da276fc44bflorian/* Initialise the string table for segment names. It contains an empty 400346ee2f7978bf2ab1ead4982e56870da276fc44bflorian string which is not referenced. */ 401346ee2f7978bf2ab1ead4982e56870da276fc44bflorianvoid 4024ecd48360351f666f008148c12a24cbda455c6b1florianML_(am_segnames_init)(void) 403346ee2f7978bf2ab1ead4982e56870da276fc44bflorian{ 404346ee2f7978bf2ab1ead4982e56870da276fc44bflorian aspacem_assert(sizeof segnames >= overhead); 405346ee2f7978bf2ab1ead4982e56870da276fc44bflorian 406346ee2f7978bf2ab1ead4982e56870da276fc44bflorian segnames_used = overhead; 407346ee2f7978bf2ab1ead4982e56870da276fc44bflorian put_sentinel(segnames_used); 408346ee2f7978bf2ab1ead4982e56870da276fc44bflorian} 409346ee2f7978bf2ab1ead4982e56870da276fc44bflorian 410346ee2f7978bf2ab1ead4982e56870da276fc44bflorian/* Increase reference count of segment name identified by IX. */ 411346ee2f7978bf2ab1ead4982e56870da276fc44bflorianvoid 4124ecd48360351f666f008148c12a24cbda455c6b1florianML_(am_inc_refcount)(Int ix) 413346ee2f7978bf2ab1ead4982e56870da276fc44bflorian{ 414346ee2f7978bf2ab1ead4982e56870da276fc44bflorian if (ix != -1) 415346ee2f7978bf2ab1ead4982e56870da276fc44bflorian inc_refcount(ix); 416346ee2f7978bf2ab1ead4982e56870da276fc44bflorian} 417346ee2f7978bf2ab1ead4982e56870da276fc44bflorian 418346ee2f7978bf2ab1ead4982e56870da276fc44bflorian/* Decrease reference count of segment name identified by IX. */ 419346ee2f7978bf2ab1ead4982e56870da276fc44bflorianvoid 4204ecd48360351f666f008148c12a24cbda455c6b1florianML_(am_dec_refcount)(Int ix) 421346ee2f7978bf2ab1ead4982e56870da276fc44bflorian{ 422346ee2f7978bf2ab1ead4982e56870da276fc44bflorian if (ix != -1) 423346ee2f7978bf2ab1ead4982e56870da276fc44bflorian dec_refcount(ix); 424346ee2f7978bf2ab1ead4982e56870da276fc44bflorian} 425346ee2f7978bf2ab1ead4982e56870da276fc44bflorian 426346ee2f7978bf2ab1ead4982e56870da276fc44bflorianBool 4274ecd48360351f666f008148c12a24cbda455c6b1florianML_(am_sane_segname)(Int ix) 428346ee2f7978bf2ab1ead4982e56870da276fc44bflorian{ 429346ee2f7978bf2ab1ead4982e56870da276fc44bflorian return ix == -1 || (ix >= overhead && ix < segnames_used); 430346ee2f7978bf2ab1ead4982e56870da276fc44bflorian} 431346ee2f7978bf2ab1ead4982e56870da276fc44bflorian 432346ee2f7978bf2ab1ead4982e56870da276fc44bflorianconst HChar * 4334ecd48360351f666f008148c12a24cbda455c6b1florianML_(am_get_segname)(Int ix) 434346ee2f7978bf2ab1ead4982e56870da276fc44bflorian{ 435346ee2f7978bf2ab1ead4982e56870da276fc44bflorian return (ix == -1) ? NULL : segnames + ix; 436346ee2f7978bf2ab1ead4982e56870da276fc44bflorian} 437346ee2f7978bf2ab1ead4982e56870da276fc44bflorian 438346ee2f7978bf2ab1ead4982e56870da276fc44bflorian/*--------------------------------------------------------------------*/ 439346ee2f7978bf2ab1ead4982e56870da276fc44bflorian/*--- end ---*/ 440346ee2f7978bf2ab1ead4982e56870da276fc44bflorian/*--------------------------------------------------------------------*/ 441