/* -*- mode: C; c-basic-offset: 3; -*- */
/*--------------------------------------------------------------------*/
/*--- Segment name management aspacemgr-segnames.c ---*/
/*--------------------------------------------------------------------*/
/*
This file is part of Valgrind, a dynamic binary instrumentation
framework.
Copyright (C) 2015-2015 Florian Krohm
This program is free software; you can redistribute it and/or
modify it under the terms of the GNU General Public License as
published by the Free Software Foundation; either version 2 of the
License, or (at your option) any later version.
This program is distributed in the hope that it will be useful, but
WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
General Public License for more details.
You should have received a copy of the GNU General Public License
along with this program; if not, write to the Free Software
Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
02111-1307, USA.
The GNU General Public License is contained in the file COPYING.
*/
/* Segment names are stored in a string table.
The string table is organised into slots of varying length. Slots are
adjacent and there are no holes between slots.
A slot consists of two parts:
(1) a fixed size overhead of length 4 bytes
(2) a variable size payload of up to 65535 bytes
The segment name is stored in the payload area. Therefore:
a segment name cannot be longer than 65535 bytes including the '\0'
terminator. This looks like a reasonable limitation.
Overall slot layout:
| 4 bytes | max 65535 bytes |
+-----------------------------+-------------------------+
| overhead | payload |
+-----------------------------+-------------------------+
^ ^
| |
-4 +----- seg->fnIdx
Each slot is uniquely identified by an index which points to the first
byte of the payload area. It is this value that is stored in seg->fnIdx.
Note, that this value is at least 4.
A slot either holds a string or it is free. The status of a slot is
identified by the leftmost bit in the overhead field, the so called F-bit.
F-bit == 1 means that slot is free; otherwise it is occupied and holds a
string.
Slot containing a string (segment name):
bits | 1 | 15 | 16 |
+---+--------------+----------+-------------------------+
| 0 | refcount | slotsize | the string including \0 |
+---+--------------+----------+-------------------------+
^ ^ ^
| | |
-4 -2 +----- seg->fnIdx
Segment names are reference counted. 15 bits are available which allows
for up to 32767 references. If the string is referenced more than 32767
times, the reference count will be frozen and the slot can never
become free. I'm not unduly concerned.
Two bytes are reserved to hold the size of the slot. Well, it's actually
the size of the payload aread (i.e. the size of the slot minus the
overhead). Ah well -- the name sticks.
With two bytes to store the size, the payload area can be at most 65535
bytes large.
A free slot looks like this:
bits | 1 | 31 | 16 |
+---+-------------------------+----------+--------------+
| 1 | index of next free slot | slotsize | .. unused .. |
+---+-------------------------+----------+--------------+
^ ^
| |
-4 +----- seg->fnIdx
Free slots are chained together in a singly linked list. An index of
zero indicates the end of the chain. Note that zero cannot conflict
with an index into the string table as the minimum index is at least
four (see above).
The typical way to traverse the segment names is:
for (ix = overhead; (size = get_slotsize(ix)) != 0; ix += size + overhead) {
if (is_freeslot(ix))
do this
else
do that
}
Important detail: there is a sentinel at the end of the list, namely a
slot with a zero-sized payload area.
Whenever a new segment name needs to be stashed away, the list of free
slots is traversed and the first slot which is large enough is being taken
(first fit). There will be no splitting of slots, as that complicates
matters and without slot coalescing would lead to memory fragmentation.
So we leave it as is until a use case comes up that needs something better.
*/
#include "pub_core_basics.h" // types
#include "priv_aspacemgr.h"
// A few constants.
enum {
refcount_size = sizeof(UShort),
slotsize_size = sizeof(UShort),
overhead = refcount_size + slotsize_size,
max_refcount = 0x7fff, // 2 bytes - F-bit
max_slotsize = 0xffff, // 2 bytes
max_slotindex = 0x7fffffff, // 4 bytes - F-bit
fbit_mask_value = 0x80,
end_of_chain = 0
};
static const UInt fbit_mask = fbit_mask_value;
/* The old segname implementation allowed for 1000 names on Android and
6000 names on other platforms. Each name was allowed to be 1000 characters
long. That was very wasteful. */
#define VG_TABLE_SIZE 1000000
/* String table for segment names */
static HChar segnames[VG_TABLE_SIZE]; /* her majesty, the string table */
static SizeT segnames_used = 0; /* number of bytes used */
static UInt num_segnames = 0; /* number of names in string table */
static UInt num_slots = 0; /* number of slots in string table */
static UInt freeslot_chain = end_of_chain;
static Bool
is_freeslot(UInt ix)
{
aspacem_assert(ix >= overhead && ix <= segnames_used);
return (segnames[ix - 4] & fbit_mask) != 0;
}
static void
put_slotindex(UInt ix, UInt slotindex)
{
aspacem_assert(ix >= overhead && ix <= segnames_used);
if (slotindex != 0)
aspacem_assert(slotindex >= overhead && slotindex <= segnames_used);
slotindex |= fbit_mask << 24;
segnames[ix - 1] = slotindex & 0xFF; slotindex >>= 8;
segnames[ix - 2] = slotindex & 0xFF; slotindex >>= 8;
segnames[ix - 3] = slotindex & 0xFF; slotindex >>= 8;
segnames[ix - 4] = slotindex & 0xFF;
}
static UInt
get_slotindex(UInt ix)
{
aspacem_assert(ix >= overhead && ix <= segnames_used);
aspacem_assert(is_freeslot(ix));
// Avoid unexpected sign extension
const UChar *unames = (const UChar *)segnames;
UInt slotindex = 0;
slotindex |= unames[ix - 4]; slotindex <<= 8;
slotindex |= unames[ix - 3]; slotindex <<= 8;
slotindex |= unames[ix - 2]; slotindex <<= 8;
slotindex |= unames[ix - 1];
return slotindex & max_slotindex; // removes the F-bit
}
static void
put_slotsize(UInt ix, UInt size)
{
aspacem_assert(ix >= overhead && ix <= segnames_used);
aspacem_assert(size <= max_slotsize);
segnames[ix - 1] = size & 0xff;
segnames[ix - 2] = size >> 8;
}
static UInt
get_slotsize(UInt ix)
{
aspacem_assert(ix >= overhead && ix <= segnames_used);
// Avoid unexpected sign extension
const UChar *unames = (const UChar *)segnames;
if (is_freeslot(ix))
return (unames[ix] << 8) | unames[ix+1];
else
return (unames[ix - 2] << 8) | unames[ix - 1];
}
static void
put_refcount(UInt ix, UInt rc)
{
aspacem_assert(ix >= overhead && ix <= segnames_used);
aspacem_assert(rc <= max_refcount);
// rc <= max_refcount ensures that the F-bit is zero
segnames[ix - 3] = rc & 0xff;
segnames[ix - 4] = rc >> 8;
}
static UInt
get_refcount(UInt ix)
{
aspacem_assert(ix >= overhead && ix <= segnames_used);
// must not be a free slot
aspacem_assert(! is_freeslot(ix));
// Avoid unexpected sign extension
const UChar *unames = (const UChar *)segnames;
return (unames[ix - 4] << 8) | unames[ix - 3];
}
static void
inc_refcount(UInt ix)
{
aspacem_assert(ix >= overhead && ix <= segnames_used);
UInt rc = get_refcount(ix);
if (rc != max_refcount)
put_refcount(ix, rc + 1);
}
static void
dec_refcount(UInt ix)
{
aspacem_assert(ix >= overhead && ix <= segnames_used);
UInt rc = get_refcount(ix);
aspacem_assert(rc > 0);
if (rc != max_refcount) {
--rc;
if (rc != 0) {
put_refcount(ix, rc);
} else {
UInt size = get_slotsize(ix);
/* Chain this slot in the freelist */
put_slotindex(ix, freeslot_chain);
get_slotindex(ix);
put_slotsize(ix + slotsize_size, size);
get_slotindex(ix);
freeslot_chain = ix;
--num_segnames;
if (0) VG_(am_show_nsegments)(0, "AFTER DECREASE rc -> 0");
}
}
}
static void
put_sentinel(UInt ix)
{
aspacem_assert(ix >= overhead && ix <= segnames_used);
put_refcount(ix, 0);
put_slotsize(ix, 0);
}
/* Searches the string table to find an index for the given name.
If none is found, an index is allocated and the name stored.
If running ouf of memory, return -1. */
Int
ML_(am_allocate_segname)(const HChar *name)
{
UInt len, ix, size, next_freeslot;
aspacem_assert(name);
if (0) VG_(debugLog)(0, "aspacem", "allocate_segname %s\n", name);
len = VG_(strlen)(name);
/* First see if we already have the name. */
for (ix = overhead; (size = get_slotsize(ix)) != 0; ix += size + overhead) {
if (is_freeslot(ix)) continue;
if (VG_(strcmp)(name, segnames + ix) == 0) {
inc_refcount(ix);
return ix;
}
}
/* Is there a free slot in the string table from a previously "freed"
segment name ? */
Int prev;
for (prev = -1, ix = freeslot_chain; ix != end_of_chain;
prev = ix, ix = next_freeslot) {
next_freeslot = get_slotindex(ix); // next in chain
size = get_slotsize(ix);
if (size >= len + 1) {
/* Note, if the size of the slot is a lot larger than the length
of the string we're about to store in it, we could split the
slot into two. But that complicates matters and as we're not
doing any coalescing of adjacent free slots this could lead to
fragmentation. */
if (prev == -1)
freeslot_chain = next_freeslot;
else
put_slotindex(prev, next_freeslot);
put_refcount(ix, 1);
put_slotsize(ix, size);
VG_(strcpy)(segnames + ix, name);
++num_segnames;
return ix;
}
}
/* We need to add a new name. */
/* Note, that we need at least two bytes in the payload. The reason is
that the payload area will be used to store the size of the slot when
the slot is on the freelist. */
if (len == 0) len = 1;
/* Is there enough room in the string table? The OVERHEAD is for the
sentinel following the payload of new slot. */
SizeT need = len + 1 + overhead;
if (need > (sizeof segnames) - segnames_used) {
return -1;
}
++num_segnames;
++num_slots;
/* copy it in */
ix = segnames_used;
put_refcount(ix, 1);
put_slotsize(ix, len + 1);
VG_(strcpy)(segnames + ix, name);
segnames_used += need;
/* Add sentinel at end of segment name list */
put_sentinel(segnames_used);
return ix;
}
/* Debugging output */
void
ML_(am_show_segnames)(Int logLevel, const HChar *prefix)
{
UInt size, ix, i;
VG_(debugLog)(logLevel, "aspacem", "%u segment names in %u slots\n",
num_segnames, num_slots);
if (freeslot_chain == end_of_chain)
VG_(debugLog)(logLevel, "aspacem", "freelist is empty\n");
else
VG_(debugLog)(logLevel, "aspacem", "freelist begins at %u\n",
freeslot_chain);
for (i = 0, ix = overhead; (size = get_slotsize(ix)) != 0;
ix += size + overhead, ++i) {
if (is_freeslot(ix))
VG_(debugLog)(logLevel, "aspacem",
"(%u,%u,0) [free slot: size=%u next=%u]\n", i, ix,
get_slotsize(ix), get_slotindex(ix));
else
VG_(debugLog)(logLevel, "aspacem",
"(%u,%u,%u) %s\n", i, ix, get_refcount(ix),
segnames + ix);
}
}
/* Returns a sequence number for the fnIdx position in segnames.
Used in aspacemgr debug output to associate a segment with
a segment name. */
Int
ML_(am_segname_get_seqnr)(Int fnIdx)
{
SizeT ix, size;
Int seqnr = -1;
if (fnIdx == -1) return -1; // shortcut
for (ix = overhead; (size = get_slotsize(ix)) != 0; ix += size + overhead) {
seqnr++;
if (ix == fnIdx)
return seqnr;
}
// We should always find the given index; something's busted
aspacem_assert(0);
return -1;
}
/* Initialise the string table for segment names. It contains an empty
string which is not referenced. */
void
ML_(am_segnames_init)(void)
{
aspacem_assert(sizeof segnames >= overhead);
segnames_used = overhead;
put_sentinel(segnames_used);
}
/* Increase reference count of segment name identified by IX. */
void
ML_(am_inc_refcount)(Int ix)
{
if (ix != -1)
inc_refcount(ix);
}
/* Decrease reference count of segment name identified by IX. */
void
ML_(am_dec_refcount)(Int ix)
{
if (ix != -1)
dec_refcount(ix);
}
Bool
ML_(am_sane_segname)(Int ix)
{
return ix == -1 || (ix >= overhead && ix < segnames_used);
}
const HChar *
ML_(am_get_segname)(Int ix)
{
return (ix == -1) ? NULL : segnames + ix;
}
/*--------------------------------------------------------------------*/
/*--- end ---*/
/*--------------------------------------------------------------------*/