alloc.cpp

Go to the documentation of this file.

 
// expand _TEST_EXPORT macros
#define _RWSTD_TEST_SRC
 
#include <stdlib.h>   // for atoi(), getenv(), malloc(), free()
#include <string.h>   // for memset()
 
#include <rw_alloc.h>
#include <rw_driver.h>   // for rw_error(), rw_fatal()
 
 
#ifdef __CYGWIN__
// use the Windows API on Cygwin
#  define _WIN32
#endif
 
#ifndef _WIN32
#  ifdef __SUNPRO_CC
// working around SunOS bug #568
#    include <time.h>
#  endif
#  include <unistd.h>     // for getpagesize(), sysconf()
#  include <sys/mman.h>   // for mmap()
#  include <sys/types.h>
 
#  ifndef _SC_PAGE_SIZE
// fall back on the alternative macro if it exists,
// or use getpagesize() otherwise
#    ifndef _SC_PAGESIZE
#      define GETPAGESIZE()   getpagesize ()
#    else
#      define GETPAGESIZE()   sysconf (_SC_PAGESIZE)
#    endif
#  else
#      define GETPAGESIZE()   sysconf (_SC_PAGE_SIZE)
#  endif   // _SC_PAGE_SIZE
 
// POSIX mprotect() and munmap() take void* but some legacy systems
// still declare the functions to take char* (aliased as caddr_t)
typedef _RWSTD_MUNMAP_ARG1_T CaddrT;
 
#else   // ifdef _WIN32
 
#  include <windows.h>    // for everything (ugh)
#  include <sys/types.h>  // for off_t
#  include <errno.h>      // for errno
 
#  define GETPAGESIZE()   getpagesize ()
 
typedef void* CaddrT;
 
static long
getpagesize ()
{
    static long pagesize_ = 0;
 
    if (0 == pagesize_) {
        SYSTEM_INFO info;
        GetSystemInfo (&info);
        pagesize_ = long (info.dwPageSize);
    }
 
    return pagesize_;
}
 
enum {
    PROT_NONE  = 0,
    PROT_READ  = 1 << 0,
    PROT_WRITE = 1 << 1,
    PROT_RDWR  = PROT_READ | PROT_WRITE,
    PROT_EXEC  = 1 << 2
};
 
#define MAP_PRIVATE   0
#define MAP_ANONYMOUS 0
 
#define MAP_FAILED ((CaddrT)-1)
 
static const DWORD
_rw_prots [] = {
    PAGE_NOACCESS,
    PAGE_READONLY,
    PAGE_READWRITE,
    PAGE_READWRITE,
    PAGE_EXECUTE,
    PAGE_EXECUTE_READ,
    PAGE_EXECUTE_READWRITE,
    PAGE_EXECUTE_READWRITE
};
 
 
static inline DWORD
_rw_translate_prot (int prot)
{
    if (0 <= prot && prot < sizeof _rw_prots / sizeof *_rw_prots)
        return _rw_prots[prot];
 
    return PAGE_NOACCESS;
}
 
 
static inline CaddrT
mmap (CaddrT addr, size_t len, int prot, int, int, off_t)
{
    addr = VirtualAlloc (addr, len, MEM_RESERVE | MEM_COMMIT,
        _rw_translate_prot (prot));
 
    if (addr)
        return addr;
 
    errno = EINVAL;
    return MAP_FAILED;
}
 
 
static inline int
munmap (CaddrT addr, size_t)
{
    if (VirtualFree (addr, 0, MEM_RELEASE))
        return 0;
    
    errno = EINVAL;
    return -1;
}
 
 
static inline int
mprotect (CaddrT addr, size_t len, int prot)
{
    DWORD flOldProt;
    if (VirtualProtect (addr, len, _rw_translate_prot (prot), &flOldProt))
        return 0;
    
    errno = EINVAL;
    return -1;
}
 
#endif   // _WIN32
 
#ifndef MAP_PRIVATE
#  define MAP_PRIVATE     0
#endif   // MAP_PRIVATE
 
#ifndef MAP_ANONYMOUS
   // no MAP_ANONYMOUS on IRIX64
#  define MAP_ANONYMOUS   0
#endif   // MAP_ANONYMOUS
 
 
struct BlockInfo
{
    void*  addr_;   // address of the allocated block
                    // if addr_ == 0 block is unused
    size_t size_;   // size of the allocated block
    void*  data_;   // address of the user data
    size_t udsz_;   // size of the user data
    int    flags_;  // memory protection flags
};
 
struct Stats
{
    size_t blocks_;     // number of the current allocated blocks
    size_t maxblocks_;  // max number of the allocated blocks
};
 
 
static Stats
_rw_stats;
 
 
struct Blocks
{
    Blocks*   next_;
    size_t    nblocks_;
    BlockInfo blocks_[1];
};
 
 
static Blocks* _rw_head = 0;   // pointer to the first Blocks in list
static Blocks* _rw_tail = 0;   // pointer to the last Blocks in list
 
struct Pair
{
    void*      addr_;       // pointer to the user data in block
    BlockInfo* info_;       // pointer to the corresponding BlockInfo
};
 
static Pair*  _rw_table           = 0; // pointer to the table
static size_t _rw_table_size      = 0; // size of table in bytes
static size_t _rw_table_max_size  = 0; // max number of items in table
 
 
static Pair*
_rw_lower_bound (Pair* first, Pair* last, void* addr)
{
    for (size_t dist = last - first; dist > 0; ) {
 
        // half = dist / 2
        const size_t half = dist >> 1;
        Pair* const middle = first + half;
 
        if (middle->addr_ < addr) {
            first = middle + 1;
            dist -= half + 1;
        }
        else
            dist = half;
    }
 
    return first;
}
 
 
static inline Pair*
_rw_binary_search (Pair* first, Pair* last, void* addr)
{
    Pair* it = _rw_lower_bound (first, last, addr);
    return (it != last && it->addr_ == addr) ? it : 0;
}
 
 
// constructor sets r/w access to the specified memory pages
// destructor sets r/o access to the specified memory pages
class MemRWGuard
{
    CaddrT caddr_;
    size_t size_;
 
public:
    MemRWGuard (void* addr, size_t size) {
        static const size_t pagemask = GETPAGESIZE () - 1;
 
        // check that pagesize is power of 2
        RW_ASSERT (0 == ((pagemask + 1) & pagemask));
 
        // caddr_ should be aligned to memory page boundary
        const size_t off = size_t (addr) & pagemask;
 
        addr = _RWSTD_STATIC_CAST (char*, addr) - off;
 
        caddr_ = _RWSTD_STATIC_CAST (CaddrT, addr);
        size_  = size + off;
 
        const int res = mprotect (caddr_, size, PROT_READ | PROT_WRITE);
        rw_error (0 == res, __FILE__, __LINE__,
                  "mprotect failed: errno = %{#m} (%{m})");
    }
 
    ~MemRWGuard () {
        const int res = mprotect (caddr_, size_, PROT_READ);
        rw_error (0 == res, __FILE__, __LINE__,
                  "mprotect failed: errno = %{#m} (%{m})");
    }
 
private:
    // not defined
    MemRWGuard (const MemRWGuard&);
    MemRWGuard& operator= (const MemRWGuard&);
};
 
 
static void
_rw_table_free ()
{
    if (!_rw_table)
        return;
 
    const CaddrT caddr = _RWSTD_REINTERPRET_CAST (CaddrT, _rw_table);
 
    const int res = munmap (caddr, _rw_table_size);
    rw_error (0 == res, __FILE__, __LINE__,
              "munmap(%#p, %zu) failed: errno = %{#m} (%{m})",
              _rw_table, _rw_table_size);
 
    _rw_table          = 0;
    _rw_table_size     = 0;
    _rw_table_max_size = 0;
}
 
 
static bool
_rw_table_grow ()
{
    // _rw_table_max_size cannot be less than allocated blocks
    RW_ASSERT (_rw_table_max_size >= _rw_stats.blocks_);
 
    // check for free space in current table
    if (_rw_table_max_size == _rw_stats.blocks_) {
        // realloc more memory
        static const size_t pagesize = GETPAGESIZE ();
 
        const size_t new_size = _rw_table_size + pagesize;
 
        const CaddrT caddr = mmap (0, new_size,
                                   PROT_READ | PROT_WRITE,
                                   MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);
 
        if (MAP_FAILED == caddr)
            // no memory available
            return false;
 
        // copy old table
        memcpy (caddr, _rw_table, _rw_stats.blocks_ * sizeof (Pair));
 
        // protect the new table
        const int res = mprotect (caddr, new_size, PROT_READ);
        rw_error (0 == res, __FILE__, __LINE__,
                  "mprotect(%#p, %zu, PROT_READ) failed: errno = %{#m} (%{m})",
                  caddr, new_size);
 
        // free old table
        _rw_table_free ();
 
        _rw_table          = _RWSTD_REINTERPRET_CAST (Pair*, caddr);
        _rw_table_size     = new_size;
        _rw_table_max_size = new_size / sizeof (Pair);
    }
 
    return true;
}
 
 
// inserts info about newly created BlockInfo
// increments the number of the allocated blocks
static void
_rw_table_insert (BlockInfo& info)
{
    Pair* const begin = _rw_table;
    Pair* const end   = begin + _rw_stats.blocks_;
    Pair* const it    = _rw_lower_bound (begin, end, info.data_);
 
    {
        MemRWGuard guard (_rw_table, _rw_table_size);
 
        // move items [it, end) to the end of table
        memmove (it + 1, it, (end - it) * sizeof (Pair));
 
        it->addr_ = info.data_;
        it->info_ = &info;
    }
 
    ++_rw_stats.blocks_;
    if (_rw_stats.blocks_ > _rw_stats.maxblocks_)
        _rw_stats.maxblocks_ = _rw_stats.blocks_;
}
 
 
// removes the specified item from table
// decrements the number of the allocated blocks
static void
_rw_table_remove (Pair* it)
{
    const size_t index = size_t (it - _rw_table);
 
    rw_fatal (index < _rw_stats.blocks_, __FILE__, __LINE__,
              "invalid index in _rw_table_remove: %zu", index);
 
    MemRWGuard guard (_rw_table, _rw_table_size);
    memmove (it, it + 1, (--_rw_stats.blocks_ - index) * sizeof (Pair));
}
 
 
// allocate more blocks (allocates one memory page)
static bool
_rw_allocate_blocks ()
{
    // count of the blocks per memory page
    static size_t blocks_per_page = 0;
 
    static const size_t pagesize = GETPAGESIZE ();
 
    if (0 == blocks_per_page)
        blocks_per_page = (pagesize - sizeof (Blocks)) / sizeof (BlockInfo) + 1;
 
    const CaddrT caddr = mmap (0, pagesize,
                               PROT_READ | PROT_WRITE,
                               MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);
 
    if (MAP_FAILED != caddr) {
 
        memset (caddr, 0, pagesize);
 
        Blocks* const blocks = _RWSTD_REINTERPRET_CAST (Blocks*, caddr);
 
        blocks->nblocks_ = blocks_per_page;
 
        // set r/o access to the new page
        const int res = mprotect (caddr, pagesize, PROT_READ);
        rw_error (0 == res, __FILE__, __LINE__,
                  "mprotect(%#p, %zu, PROT_READ) failed: errno = %{#m} (%{m})",
                  caddr, pagesize);
 
        if (0 == _rw_head)
            _rw_head = blocks;
        else {
            MemRWGuard guard (&_rw_tail->next_, sizeof (_rw_tail->next_));
            _rw_tail->next_ = blocks;
        }
 
        _rw_tail = blocks;
 
        return true;
    }
 
    return false;
}
 
 
// free allocated blocks
// should be called when all user memory allocated
// by rw_alloc were freed by rw_free
static void
_rw_free_blocks ()
{
    rw_fatal (0 == _rw_stats.blocks_, __FILE__, __LINE__,
              "_rw_free_blocks called when %zu blocks are not freed",
              _rw_stats.blocks_);
 
    static const size_t pagesize = GETPAGESIZE ();
 
    while (_rw_head) {
        const CaddrT caddr = _RWSTD_REINTERPRET_CAST (CaddrT, _rw_head);
 
        _rw_head = _rw_head->next_;
 
        const int res = munmap (caddr, pagesize);
 
        rw_error (0 == res, __FILE__, __LINE__,
                  "munmap(%#p, %zu) failed: errno = %{#m} (%{m})",
                  caddr, pagesize);
    }
 
    _rw_tail = 0;
}
 
 
static BlockInfo*
_rw_find_unused_from (Blocks* it)
{
    while (it) {
        for (size_t i = 0; i < it->nblocks_; ++i) {
            BlockInfo & info = it->blocks_ [i];
            if (0 == info.addr_)
                return &info;
        }
 
        it = it->next_;
    }
 
    return 0;
}
 
 
// returns pointer to the first unused BlockInfo
// if none unused items tries allocate more blocks
// returns 0 if no memory
static BlockInfo*
_rw_find_unused ()
{
    BlockInfo * res = _rw_find_unused_from (_rw_head);
 
    if (!res && _rw_allocate_blocks ()) {
        // find the unused block from newly allocated blocks
        // res = _rw_find_unused_from (_rw_tail);
        res = _rw_tail->blocks_;
        // res should be != 0
        rw_fatal (0 != res, __FILE__, __LINE__,
                  "logic error in _rw_find_unused: res == 0 after "
                  "_rw_allocate_blocks() succeeded ");
    }
 
    return res;
}
 
 
// returns pointer to the Pair which corresponds to addr
// returns 0 if addr is not valid pointer, returned by rw_alloc
static Pair*
_rw_find_by_addr (void* addr)
{
    Pair* const end = _rw_table + _rw_stats.blocks_;
    return _rw_binary_search (_rw_table, end, addr);
}
 
 
static inline int
_rw_get_prot (int flags)
{
    return (flags & RW_PROT_READ  ? PROT_READ  : 0)
         | (flags & RW_PROT_WRITE ? PROT_WRITE : 0);
}
 
 
static inline int
_rw_getenvflags ()
{
    const char* const envvar = getenv ("RWSTD_ALLOC_FLAGS");
    if (envvar)
        return atoi (envvar);
 
    return 0;
}
 
 
_TEST_EXPORT void*
rw_alloc (size_t nbytes, int flags /* = -1 */)
{
    static const int RWSTD_ALLOC_FLAGS = _rw_getenvflags ();
 
    // redefine flags if environment variable was set
    if (-1 == flags && 0 != RWSTD_ALLOC_FLAGS)
        flags = RWSTD_ALLOC_FLAGS;
 
    // make sure that table has free space
    if (!_rw_table_grow ())
        return 0;
 
    if (BlockInfo *info = _rw_find_unused ()) {
 
        BlockInfo newinfo = BlockInfo ();
 
        newinfo.udsz_ = nbytes;
        newinfo.flags_ = flags;
 
        if (-1 == flags) {
 
            newinfo.addr_ = malloc (nbytes);
 
            if (newinfo.addr_) {
                newinfo.size_ = nbytes;
                newinfo.data_ = newinfo.addr_;
            }
        }
        else {
            static const size_t pagesize = GETPAGESIZE ();
 
            size_t size = nbytes + pagesize;
 
            // check that pagesize is power of 2
            RW_ASSERT (0 == (pagesize & (pagesize - 1)));
            size_t offset = size & (pagesize - 1);
 
            if (offset) {
                offset = pagesize - offset;
                size += offset;
            }
 
            newinfo.addr_ = mmap (0, size, _rw_get_prot(flags),
                                  MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);
 
            if (MAP_FAILED != newinfo.addr_) {
 
                char* data = _RWSTD_STATIC_CAST (char*, newinfo.addr_);
                char* guard = data;
                
                if (RW_PROT_BELOW & flags)
                    offset = pagesize;
                else
                    guard += size - pagesize;
 
                // deny access to the guard page
                int res = mprotect (guard, pagesize, PROT_NONE);
                rw_error (0 == res, __FILE__, __LINE__,
                          "mprotect failed: errno = %{#m} (%{m})");
 
                newinfo.size_ = size;
                newinfo.data_ = data + offset;
            }
        }
 
        if (newinfo.data_) {
 
            {
                MemRWGuard guard (info, sizeof (*info));
                *info = newinfo;
            }
 
            _rw_table_insert (*info);
 
            return info->data_;
        }
    }
 
    return 0;
}
 
 
_TEST_EXPORT void
rw_free (void* addr)
{
    if (Pair *it = _rw_find_by_addr (addr)) {
 
        BlockInfo &info = *it->info_;
 
        if (-1 == info.flags_)
            free (addr);
        else {
            const CaddrT caddr = _RWSTD_REINTERPRET_CAST (CaddrT, info.addr_);
 
            const int res = munmap (caddr, info.size_);
            rw_error (0 == res, __FILE__, __LINE__,
                      "munmap(%#p, %zu) failed: errno = %{#m} (%{m})",
                      caddr, info.size_);
        }
 
        {
            MemRWGuard guard (&info, sizeof (info));
            info = BlockInfo ();
        }
 
        _rw_table_remove (it);
 
        if (0 == _rw_stats.blocks_) {
            _rw_free_blocks ();
            _rw_table_free ();
        }
    }
    else
        rw_error (0 == addr, __FILE__, __LINE__,
                  "rw_free(%#p): the address is not a valid address, "
                  "returned by rw_alloc()",
                  addr);
}