/* -*- 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                                                          ---*/
/*--------------------------------------------------------------------*/