get.c

/* 
 shm-arena    shared memory arena
 Copyright (C) 2006-2008 Lance Arsenault (LGPL v3)


    This file is part of shm-arena.

    shm-arena is free software; you can redistribute it and/or modify
    it under the terms of the GNU Lesser General Public License as
    published by the Free Software Foundation; either version 3 of the
    License, or (at your option) any later version.

    shm-arena 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
    Lesser General Public License for more details.

    You should have received a copy of the GNU Lesser General Public
    License along with this program.  If not, see
    <http://www.gnu.org/licenses/>.
*/

#include "config.h"
#include <stdio.h>
#include <sys/types.h>
#include <sys/stat.h>
#include <fcntl.h>
#include <errno.h>
#include <string.h>
#include <unistd.h>
#include <stdlib.h>
#include <sys/mman.h>
#include <stdint.h>
#include <pthread.h>

#include "spew.h"
#include "assert.h"
#include "debug_lock.h"
#include "shm_arena.h"
#include "arena.h"
#include "arena_lock.h"
#include "avl.h"

#define DEFAULT_NAME_PREFIX    "~"
#define DEFAULT_NAME_SUFFIX    "~"


static inline
void *allocate_segment(struct shm_arena *a,
               const char *name, size_t size,
               int with_rwlock)
{
  size_t total_seg_size; /* total size needed for the allocated segment */
  struct seg_header *seg;
  mapnum_t mapnum = -1;
  struct seg_footer *fdr;

  SPEW(_DEBUG, "Creating segment \"%s\" with size=%zu",
       name, size);

  ASSERT(a->change_count == ((struct arena_header *)
                 (a->mapping[0].start))->change_count);
  ASSERT(a->num_mappings == ((struct arena_header *)
                 (a->mapping[0].start))->num_mappings);

  /* total size needed for the allocated segment */
  total_seg_size =
    CHUNKS(sizeof(struct seg_header)) +
    CHUNKS(size) +
    (with_rwlock?CHUNKS(sizeof(pthread_rwlock_t)):0) +
    CHUNKS(strlen(name)+1) +
    CHUNKS(sizeof(struct seg_footer));

  seg = find_free_segment(a, total_seg_size, &mapnum);

  /********************************************************/
  /**** There are 6 cases of code paths to check here. ****/
  /********************************************************/

  if(seg)
    {
      /* We found a big enough free segment. */

#ifdef SHM_DEBUG
      int detach_err;
      detach_err =
#endif

      _shm_detach_free_segment(a, seg, mapnum);

      ASSERT(!detach_err);

      if(seg->length*CHUNK >= (CHUNKS(sizeof(struct seg_header)) +
      total_seg_size + CHUNKS(sizeof(struct seg_footer))))
    {
      /* We will split the segment into two, first the allocated
       * one and then a free one. So if the free one is at the end
       * of the last mapping we can truncate the arena file, and
       * maybe unmap it. */
      struct seg_header *free_hdr;

      SPEW(_DEBUG, "Case 1: Found Free & Split");

      /* This is where the free memory will be. */
      free_hdr = (struct seg_header *)(((uint8_t *)seg) + total_seg_size);

      free_hdr->length = (seg->length*CHUNK - total_seg_size)/CHUNK;
      fdr = (struct seg_footer *)
        (((uint8_t *)free_hdr) + (free_hdr->length*CHUNK -
                      CHUNKS(sizeof(struct seg_footer))));
      fdr->length = free_hdr->length;
      fdr->flags = IS_FREE;

      seg->length = total_seg_size/CHUNK;

      insert_free_segment(a, free_hdr, mapnum);
    }
#ifdef WITH_SPEW
      else
    {
      /* else *
           * We are not slitting the segment.  We'll just use what we
       * found. */
      /* The seg->length does not change. */
      SPEW(_DEBUG, "Case 2: Found Free With This Size");
    }
#endif /*#ifdef SHM_DEBUG */

    }
  else /* make more shared memory */
    {
      /* Here we make more memory by extending the arena file and
       * mapping more if required.  There could be more memory
       * available in the last mapping.  All other mappings would have
       * free segments that would have been found with
       * find_free_segment() above if they were big enough. */
      struct mapping_header *mhdr = NULL;
      struct stat st;

      if(fstat(a->fd, &st)) /* Get the size of the arena file. */
    return /* We are screwed now. */
      SPEW_SYS_ERR_RET(NULL, _WARN, errno,
               "fstat(fd=%d,) failed", a->fd);

      mhdr = get_mapping_header(a, a->num_mappings-1);

#ifdef SHM_DEBUG
      if(mhdr->length_used*CHUNK >
     (CHUNKS(sizeof(struct mapping_header)) +
      ((a->num_mappings-1 == 0)?CHUNKS(sizeof(struct arena_header)):0)))
    {
      /* We can find the footer in the last segment at the end of
       * the mapping, if there are any segments at all. */
      fdr = (struct seg_footer *)
        (a->mapping[a->num_mappings-1].start +
         ((mhdr->length_used*CHUNK - CHUNKS(sizeof(struct seg_footer)))));

      /* The last segment in the last mapping should not be free,
       * otherwise it would have been removed.  We have a coding
       * error if it is free. */
      ASSERT(!(fdr->flags & IS_FREE));
    }
#endif /* #ifdef SHM_DEBUG */


      if((mhdr->map_length - mhdr->length_used)*CHUNK >= total_seg_size)
    {
      SPEW(_DEBUG, "Case 3: Ftrunate & Add Segment");
      /* We extend the end of the arena file in the last mapping,
       * without adding another mapping. */

      mapnum = a->num_mappings - 1;

      ASSERT(st.st_size >= (off_t) (mhdr->length_used*CHUNK));

      if(ftruncate(a->fd, st.st_size + total_seg_size))
        return /* Shit. */
          SPEW_SYS_ERR_RET(NULL, _WARN, errno,
                   "ftruncate(fd=%d,) failed", a->fd);

      SPEW(_DEBUG, "Total arena file size has increased to %lu bytes",
           st.st_size + total_seg_size);

      
      /* The memory will be at what was the end of the last
       * mapping. */
      seg = (struct seg_header *)
        (a->mapping[mapnum].start + mhdr->length_used*CHUNK);

      mhdr->length_used += total_seg_size/CHUNK;
    }
      else
    {
      /* We need to create a new arena file mapping */
      void *map_start = NULL;
      int pagesize;
      off_t old_map_end;

      ASSERT(mhdr->map_length >= mhdr->length_used);

      pagesize = getpagesize();

      /* First we need to pad in the end of the arena file with a
       * free segment, or extend the last segment if it's not big
       * enough to hold a free segment, plus the size needed and
       * used in the new mapping to come. */
      old_map_end = st.st_size + (mhdr->map_length - mhdr->length_used)*CHUNK;

      if(ftruncate(a->fd, old_map_end +
               total_seg_size + CHUNKS(sizeof(struct mapping_header))))
        return /* error */
          SPEW_SYS_ERR_RET(NULL, _WARN, errno,
                   "ftruncate(fd=%d,) failed", a->fd);

      SPEW(_DEBUG, "Total arena file size has increased to %lu bytes",
           old_map_end + total_seg_size + CHUNKS(sizeof(struct mapping_header)));

      if(mhdr->map_length - mhdr->length_used >=
         CHUNKS(sizeof(struct seg_header)) + CHUNKS(sizeof(struct seg_footer)))
        {
          SPEW(_DEBUG, "Case 4: Ftrunate & Add Free Pad & Add Mapping");
          /* add a free memory to the end of the mapping */

          /* adding one free segment to the end of the mapping
           * before we add the next mapping with an allocated
           * segment at the top. */
          seg = (struct seg_header *) /* using seg as a dummy var */
        (a->mapping[a->num_mappings-1].start + mhdr->length_used*CHUNK);

          seg->length = mhdr->map_length - mhdr->length_used;
          seg->left_mapnum = -1;
          seg->right_mapnum = -1;
          seg->left_offset = 0;
          seg->right_offset = 0;

          /* Put a footer the new end of the mapping. */
          fdr = (struct seg_footer *)
        (((uint8_t *) seg) + (seg->length*CHUNK -
                    CHUNKS(sizeof(struct seg_footer))));
          fdr->length = seg->length;
          fdr->flags = IS_FREE;

          mhdr->length_used = mhdr->map_length;

          insert_free_segment(a, seg, a->num_mappings-1);
        }
      else if(mhdr->map_length > mhdr->length_used)
        {
          SPEW(_DEBUG, "Case 5: Ftrunate & Add Pad To Last Segment & Add Mapping");
          /* We have an unusable small piece of memory at the end
           * of the mapping, so we must put it in the last segment
           * in the mapping so that we do not leak it. */
          fdr = (struct seg_footer *)
        (a->mapping[a->num_mappings-1].start +
         ((mhdr->length_used*CHUNK - CHUNKS(sizeof(struct seg_footer)))));

          seg = (struct seg_header *) /* using seg as a dummy var */
        (((uint8_t *) fdr) -
         (fdr->length*CHUNK - CHUNKS(sizeof(struct seg_footer))));

          seg->length += mhdr->map_length - mhdr->length_used;

          /* The footer moves to the bottom of the now longer segment. */
          fdr = (struct seg_footer *)
        (((uint8_t *) seg) +
         (seg->length*CHUNK - CHUNKS(sizeof(struct seg_footer))));

          fdr->flags = 0;
          if(with_rwlock) fdr->flags |= WITH_RWLOCK;
          fdr->length = seg->length;

          mhdr->length_used = mhdr->map_length;
        }
#ifdef WITH_SPEW
      else
        {
          /* mhdr->map_length == mhdr->length_used */
          SPEW(_DEBUG, "Case 6: Ftrunate & Add Mapping");
        }
#endif

      /* now add the new mapping and create a segment. */
      mapnum = a->num_mappings;
      (a->num_mappings)++;
      a->mapping = (struct shm_mapping *)
        realloc(a->mapping, a->num_mappings*sizeof(struct shm_mapping));

      if(!(a->mapping))
        return /* error */
          SPEW_SYS_ERR_RET(NULL, _WARN, errno, "realloc() failed");

      a->mapping[mapnum].map_length =
        PAGES(total_seg_size + CHUNKS(sizeof(struct mapping_header)),
          pagesize);
      if(a->user_shm_address)
        /* If this arena struct was created when env SHM_ADDRESS was set. */
        map_start = (void*)(((uintptr_t) a->mapping[mapnum-1].start) +
        a->mapping[mapnum-1].map_length*CHUNK);
      a->mapping[mapnum].start =
        mmap(map_start, a->mapping[mapnum].map_length, PROT_READ|PROT_WRITE,
         MAP_SHARED, a->fd, old_map_end);


      /* map_length in CHUNKs */
      a->mapping[mapnum].map_length /= CHUNK;

      if(a->mapping[mapnum].start == MAP_FAILED)
        {
          (a->num_mappings)--;
          return /* error */
        SPEW_SYS_ERR_RET(NULL, _WARN, errno, "mmap() failed");
        }
      else if(a->user_shm_address && a->mapping[mapnum].start != map_start)
        {
          (a->num_mappings)--;
          errno = EFAULT;
          return /* error */
        SPEW_SYS_ERR_RET(NULL, _WARN, errno,
            "mmap() failed with SHM_ADDRESS set");
        }

      /* sync the arena change_count */
      a->change_count = ++(a->header->change_count);

      (a->header->num_mappings)++;


      mhdr = get_mapping_header(a, mapnum);

      mhdr->map_length = a->mapping[mapnum].map_length;

      mhdr->length_used =
        (CHUNKS(sizeof(struct mapping_header)) + total_seg_size)/CHUNK;

      seg = (struct seg_header *)
        (a->mapping[mapnum].start + CHUNKS(sizeof(struct mapping_header)));

      SPEW(_DEBUG, "Created new mapping of %zu pages = %zu bytes",
           mhdr->map_length*CHUNK/pagesize, mhdr->map_length*CHUNK);
    }      

      seg->length = total_seg_size/CHUNK; /* in units of CHUNKs. */
    }

  /* The allocated/named memory will start after seg. seg points
   * to its struct seg_header that is before the user
   * data and then name string. */

  seg->user_length = size;
  seg->left_mapnum = -1;
  seg->right_mapnum = -1;
  seg->left_offset = 0;
  seg->right_offset = 0;
  fdr = (struct seg_footer *)
    (((uint8_t *)seg) + (seg->length*CHUNK - CHUNKS(sizeof(struct seg_footer))));
  fdr->length = seg->length;
  fdr->flags = 0;
  if(with_rwlock) fdr->flags |= WITH_RWLOCK;

  strcpy(get_seg_name(seg), name);

  insert_alloc_segment(a, seg, mapnum);

  if(with_rwlock)
    {
      int err;
      pthread_rwlockattr_t attr;
      if((err = pthread_rwlockattr_init(&attr)))
    return
      SPEW_SYS_ERR_RET(NULL, _WARN, err, "pthread_rwlockattr_init() failed");
      if((err = pthread_rwlockattr_setpshared(&attr, PTHREAD_PROCESS_SHARED)))
    return
      SPEW_SYS_ERR_RET(NULL, _WARN, err, "pthread_rwlockattr_setpshared() failed");
      if((err = pthread_rwlock_init(get_seg_rwlock(seg), &attr)))
    return
      SPEW_SYS_ERR_RET(NULL, _WARN, err, "pthread_rwlock_init() failed");
      SPEW(_DEBUG, "Initialized segment rwlock");
    }

  return get_seg_ptr(seg);
}

void *shm_get(shm_arena_t arena, size_t size, const char *name, int flags)
{
  char gen_name[GEN_NAME_SIZE] = "";
  void *ret_ptr = NULL;
  int err = 0;

  SPEW(_INFO, "%s(arena=%p, size=%zu, name=\"%s\", flags=%d)",
       __func__, arena, (size==SHM_UNKNOWN_SIZE)?0:size,
       name, flags);

  if((!name || !name[0]) && !((flags & O_CREAT) && (flags & O_EXCL)))
    /* name is not set, so we must be creating a segment */
    return SPEW_SYS_ERR_RET(NULL, _WARN, EINVAL,
                "%s() failed: flags O_CREAT and "
                "O_EXCL bits must be set if name "
                "is not set", __func__);

  if((flags & O_CREAT) && size == SHM_UNKNOWN_SIZE)
    return SPEW_SYS_ERR_RET(NULL, _WARN, EINVAL,
                "%s() failed: O_CREAT is set "
                "and size == SHM_UNKNOWN_SIZE",
                __func__);

  /* This will get the arena object and in case it creates the arena
   * file we give the first mapping a size that is at least big enough
   * to hold this new segment, in case size is larger than one
   * page. */
  arena = get_arena_min_size_and_autolock(arena,
              (flags & O_CREAT)?  2/* write */:  1/* read */,
              &err IF_SPEW(, __func__), size);
  if(!arena)
    {
      ASSERT(err);
      errno = err;
      return NULL;
    }

  ASSERT(arena->header);

  /* Make sure that we have the current number of memory mappings for
   * this arena file, by comparing the local and arena file
   * change_count.
   *
   * On mutex locking:
   *
   * Case 1: We have an arena file write lock from the O_CREATE flag:
   * We are excluding all other threads, so we do not need a mutex
   * lock at all.
   *
   * Case 2: We have an arena file read lock: The arena file read lock
   * will stop any allocations, but we may be out of sync in which
   * case we need to change the local arena object mapping data, and
   * so we need a mutex lock to change it, because other threads may
   * be doing the same thing.  After this syncing we are guaranteed
   * that the mapping data will not change while we keep the arena
   * file read lock.  We will not be allocating in this case.
   */

  if(!(flags & O_CREAT))
    pthread_mutex_lock(&arena->mapping_mutex);
  if(arena->change_count != arena->header->change_count)
    if(_shm_arena_sync_mappings(IF_SPEW(__func__,) arena))
      {
    pthread_mutex_unlock(&arena->mapping_mutex);
    /* errno should already be set */
    goto shm_get_ret;
      }
  if(!(flags & O_CREAT))
    pthread_mutex_unlock(&arena->mapping_mutex);

  /* The mappings will stay in sync or we will be messing with them
   * here in this one thread if we allocate.  We have the arena file
   * write lock to block all other threads if we are allocating.  We
   * have a arena file read lock which will the mapping data fixed
   * until we release the arena file read lock. */

  if(!name || !name[0])
    {
      if(!((flags & O_CREAT) && (flags & O_EXCL)))
    {
      err = EINVAL; /* "Invalid argument" */
      SPEW_SYS_ERR(_WARN, EINVAL,
               "%s() failed: flags O_CREAT and "
               "O_EXCL bits must be set if segment name "
               "is not set", __func__);
      goto shm_get_ret;
    }
      /* generate a new segment name */

      for(ret_ptr = (void *) 1; ret_ptr; (arena->header->name_count)++)
    {
      snprintf(gen_name, GEN_NAME_SIZE,
           DEFAULT_NAME_PREFIX"%u"DEFAULT_NAME_SUFFIX,
           arena->header->name_count);
      ret_ptr = find_segment_name(arena, gen_name, NULL);
    }
      name = gen_name;
      SPEW(_DEBUG, "Generated segment name \"%s\"", name);
    }
  else /* we have a name string from the user */
    {
      size_t user_size;

      ret_ptr = find_segment_name(arena, name, &user_size);

      if((flags & O_CREAT) && (flags & O_EXCL) && ret_ptr)
    {
      SPEW_SYS_ERR(_WARN, EINVAL,
               "%s() failed: flags O_CREAT and "
               "O_EXCL bits must not be set: segment named "
               "\"%s\" exists.", __func__, name);
      err = EBADRQC; /* "Invalid request code" */
      goto shm_get_ret;
    }
      else if(!ret_ptr && !(flags & O_CREAT))
    {
      /* This case is NOT an ERROR: we still return NULL but the
       * err and errno is not set.  We need this to not be an
       * error so that a user can use it to test if a segment
       * exists. */
      SPEW(_INFO,
           "%s() failed: flag O_CREAT is not set and segment named "
           "\"%s\" does not exist.", __func__, name);
      goto shm_get_ret;
    }
      else if(ret_ptr)
    {
      /* return an existing segment if it's the right size */
      if(user_size != size && size != SHM_UNKNOWN_SIZE)
        {
          /* This sucks as an error code, but it's better than
           * none. */
          err = EADDRINUSE; /*  "Address already in use" */
          SPEW_SYS_ERR(_WARN, EINVAL,
               "%s() failed: segment \"%s\" exists and has "
               "a size %zu bytes not %zu bytes", __func__,
               name, user_size, size);
        }
      else
        { 
          struct seg_header *seg;
          seg = (struct seg_header *)
        (((uint8_t *) ret_ptr) - CHUNKS(sizeof(struct seg_header)));
          if(get_seg_footer(seg)->flags & WITH_RWLOCK &&
         flags & SHM_WITHOUT_RWLOCK)
        {
          err = EADDRINUSE; /*  "Address already in use" */
          SPEW_SYS_ERR(_WARN, EINVAL,
                   "%s() failed: segment \"%s\" exists and has "
                   "read-write locks. SHM_WITHOUT_RWLOCK"
                   " should not be set.",
                   __func__, name);
        }
          else if(!(get_seg_footer(seg)->flags & WITH_RWLOCK) &&
              !(flags & SHM_WITHOUT_RWLOCK))
        {
          err = EADDRINUSE; /*  "Address already in use" */
          SPEW_SYS_ERR(_WARN, EINVAL,
                   "%s() failed: segment \"%s\" exists and has "
                   "no read-write locks. SHM_WITHOUT_RWLOCK"
                   " should be set.",
                   __func__, name);
        }
#ifdef WITH_SPEW
          else
        {
          if(size == SHM_UNKNOWN_SIZE)
            size = seg->user_length;
          SPEW(_INFO, "Connected to existing segment \"%s\" with size %zu bytes",
               name, size);
        }
#endif
        }
      goto shm_get_ret;
    }
      /* Else -- we will create it outside this block. */
    }

  /* we can and need to create a new segment with name string name */
  /* We must have an arena write lock so we do not need a mutex lock
   * here. */
  ret_ptr = allocate_segment(arena, name, size, !(flags & SHM_WITHOUT_RWLOCK));


#ifdef WITH_SPEW
  if(ret_ptr)
    SPEW(_INFO, "Created segment \"%s\" with size %zu bytes", name, size);
  else
    SPEW(_WARN, "Failed to create segment \"%s\" with size %zu bytes", name, size);
#endif

 shm_get_ret:

  if(!err)
    err = arena_autounlock(arena IF_SPEW(, __func__));
  else
    arena_autounlock(arena IF_SPEW(, __func__));

  if(err)
    {
      errno = err;
      ret_ptr = NULL;
    }

  return ret_ptr;
}