/* [<][>][^][v][top][bottom][index][help] */
DEFINITIONS
This source file includes following definitions.
- find_block_by_offset
- find_block_of_size
- move_block
- APU_DECLARE
- APU_DECLARE
- APU_DECLARE
- APU_DECLARE
- APU_DECLARE
- APU_DECLARE
- APU_DECLARE
- APU_DECLARE
- APU_DECLARE
- APU_DECLARE
- APU_DECLARE
/* Licensed to the Apache Software Foundation (ASF) under one or more
* contributor license agreements. See the NOTICE file distributed with
* this work for additional information regarding copyright ownership.
* The ASF licenses this file to You under the Apache License, Version 2.0
* (the "License"); you may not use this file except in compliance with
* the License. You may obtain a copy of the License at
*
* http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing, software
* distributed under the License is distributed on an "AS IS" BASIS,
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
* See the License for the specific language governing permissions and
* limitations under the License.
*/
#include "apr_general.h"
#include "apr_rmm.h"
#include "apr_errno.h"
#include "apr_lib.h"
#include "apr_strings.h"
/* The RMM region is made up of two doubly-linked-list of blocks; the
* list of used blocks, and the list of free blocks (either list may
* be empty). The base pointer, rmm->base, points at the beginning of
* the shmem region in use. Each block is addressable by an
* apr_rmm_off_t value, which represents the offset from the base
* pointer. The term "address" is used here to mean such a value; an
* "offset from rmm->base".
*
* The RMM region contains exactly one "rmm_hdr_block_t" structure,
* the "header block", which is always stored at the base pointer.
* The firstused field in this structure is the address of the first
* block in the "used blocks" list; the firstfree field is the address
* of the first block in the "free blocks" list.
*
* Each block is prefixed by an "rmm_block_t" structure, followed by
* the caller-usable region represented by the block. The next and
* prev fields of the structure are zero if the block is at the end or
* beginning of the linked-list respectively, or otherwise hold the
* address of the next and previous blocks in the list. ("address 0",
* i.e. rmm->base is *not* a valid address for a block, since the
* header block is always stored at that address).
*
* At creation, the RMM region is initialized to hold a single block
* on the free list representing the entire available shm segment
* (minus header block); subsequent allocation and deallocation of
* blocks involves splitting blocks and coalescing adjacent blocks,
* and switching them between the free and used lists as
* appropriate. */
typedef struct rmm_block_t {
apr_size_t size;
apr_rmm_off_t prev;
apr_rmm_off_t next;
} rmm_block_t;
/* Always at our apr_rmm_off(0):
*/
typedef struct rmm_hdr_block_t {
apr_size_t abssize;
apr_rmm_off_t /* rmm_block_t */ firstused;
apr_rmm_off_t /* rmm_block_t */ firstfree;
} rmm_hdr_block_t;
#define RMM_HDR_BLOCK_SIZE (APR_ALIGN_DEFAULT(sizeof(rmm_hdr_block_t)))
#define RMM_BLOCK_SIZE (APR_ALIGN_DEFAULT(sizeof(rmm_block_t)))
struct apr_rmm_t {
apr_pool_t *p;
rmm_hdr_block_t *base;
apr_size_t size;
apr_anylock_t lock;
};
static apr_rmm_off_t find_block_by_offset(apr_rmm_t *rmm, apr_rmm_off_t next,
apr_rmm_off_t find, int includes)
{
apr_rmm_off_t prev = 0;
while (next) {
struct rmm_block_t *blk = (rmm_block_t*)((char*)rmm->base + next);
if (find == next)
return next;
/* Overshot? */
if (find < next)
return includes ? prev : 0;
prev = next;
next = blk->next;
}
return includes ? prev : 0;
}
static apr_rmm_off_t find_block_of_size(apr_rmm_t *rmm, apr_size_t size)
{
apr_rmm_off_t next = rmm->base->firstfree;
apr_rmm_off_t best = 0;
apr_rmm_off_t bestsize = 0;
while (next) {
struct rmm_block_t *blk = (rmm_block_t*)((char*)rmm->base + next);
if (blk->size == size)
return next;
if (blk->size >= size) {
/* XXX: sub optimal algorithm
* We need the most thorough best-fit logic, since we can
* never grow our rmm, we are SOL when we hit the wall.
*/
if (!bestsize || (blk->size < bestsize)) {
bestsize = blk->size;
best = next;
}
}
next = blk->next;
}
if (bestsize > RMM_BLOCK_SIZE + size) {
struct rmm_block_t *blk = (rmm_block_t*)((char*)rmm->base + best);
struct rmm_block_t *new = (rmm_block_t*)((char*)rmm->base + best + size);
new->size = blk->size - size;
new->next = blk->next;
new->prev = best;
blk->size = size;
blk->next = best + size;
if (new->next) {
blk = (rmm_block_t*)((char*)rmm->base + new->next);
blk->prev = best + size;
}
}
return best;
}
static void move_block(apr_rmm_t *rmm, apr_rmm_off_t this, int free)
{
struct rmm_block_t *blk = (rmm_block_t*)((char*)rmm->base + this);
/* close the gap */
if (blk->prev) {
struct rmm_block_t *prev = (rmm_block_t*)((char*)rmm->base + blk->prev);
prev->next = blk->next;
}
else {
if (free) {
rmm->base->firstused = blk->next;
}
else {
rmm->base->firstfree = blk->next;
}
}
if (blk->next) {
struct rmm_block_t *next = (rmm_block_t*)((char*)rmm->base + blk->next);
next->prev = blk->prev;
}
/* now find it in the other list, pushing it to the head if required */
if (free) {
blk->prev = find_block_by_offset(rmm, rmm->base->firstfree, this, 1);
if (!blk->prev) {
blk->next = rmm->base->firstfree;
rmm->base->firstfree = this;
}
}
else {
blk->prev = find_block_by_offset(rmm, rmm->base->firstused, this, 1);
if (!blk->prev) {
blk->next = rmm->base->firstused;
rmm->base->firstused = this;
}
}
/* and open it up */
if (blk->prev) {
struct rmm_block_t *prev = (rmm_block_t*)((char*)rmm->base + blk->prev);
if (free && (blk->prev + prev->size == this)) {
/* Collapse us into our predecessor */
prev->size += blk->size;
this = blk->prev;
blk = prev;
}
else {
blk->next = prev->next;
prev->next = this;
}
}
if (blk->next) {
struct rmm_block_t *next = (rmm_block_t*)((char*)rmm->base + blk->next);
if (free && (this + blk->size == blk->next)) {
/* Collapse us into our successor */
blk->size += next->size;
blk->next = next->next;
if (blk->next) {
next = (rmm_block_t*)((char*)rmm->base + blk->next);
next->prev = this;
}
}
else {
next->prev = this;
}
}
}
APU_DECLARE(apr_status_t) apr_rmm_init(apr_rmm_t **rmm, apr_anylock_t *lock,
void *base, apr_size_t size,
apr_pool_t *p)
{
apr_status_t rv;
rmm_block_t *blk;
apr_anylock_t nulllock;
if (!lock) {
nulllock.type = apr_anylock_none;
nulllock.lock.pm = NULL;
lock = &nulllock;
}
if ((rv = APR_ANYLOCK_LOCK(lock)) != APR_SUCCESS)
return rv;
(*rmm) = (apr_rmm_t *)apr_pcalloc(p, sizeof(apr_rmm_t));
(*rmm)->p = p;
(*rmm)->base = base;
(*rmm)->size = size;
(*rmm)->lock = *lock;
(*rmm)->base->abssize = size;
(*rmm)->base->firstused = 0;
(*rmm)->base->firstfree = RMM_HDR_BLOCK_SIZE;
blk = (rmm_block_t *)((char*)base + (*rmm)->base->firstfree);
blk->size = size - (*rmm)->base->firstfree;
blk->prev = 0;
blk->next = 0;
return APR_ANYLOCK_UNLOCK(lock);
}
APU_DECLARE(apr_status_t) apr_rmm_destroy(apr_rmm_t *rmm)
{
apr_status_t rv;
rmm_block_t *blk;
if ((rv = APR_ANYLOCK_LOCK(&rmm->lock)) != APR_SUCCESS) {
return rv;
}
/* Blast it all --- no going back :) */
if (rmm->base->firstused) {
apr_rmm_off_t this = rmm->base->firstused;
do {
blk = (rmm_block_t *)((char*)rmm->base + this);
this = blk->next;
blk->next = blk->prev = 0;
} while (this);
rmm->base->firstused = 0;
}
if (rmm->base->firstfree) {
apr_rmm_off_t this = rmm->base->firstfree;
do {
blk = (rmm_block_t *)((char*)rmm->base + this);
this = blk->next;
blk->next = blk->prev = 0;
} while (this);
rmm->base->firstfree = 0;
}
rmm->base->abssize = 0;
rmm->size = 0;
return APR_ANYLOCK_UNLOCK(&rmm->lock);
}
APU_DECLARE(apr_status_t) apr_rmm_attach(apr_rmm_t **rmm, apr_anylock_t *lock,
void *base, apr_pool_t *p)
{
apr_anylock_t nulllock;
if (!lock) {
nulllock.type = apr_anylock_none;
nulllock.lock.pm = NULL;
lock = &nulllock;
}
/* sanity would be good here */
(*rmm) = (apr_rmm_t *)apr_pcalloc(p, sizeof(apr_rmm_t));
(*rmm)->p = p;
(*rmm)->base = base;
(*rmm)->size = (*rmm)->base->abssize;
(*rmm)->lock = *lock;
return APR_SUCCESS;
}
APU_DECLARE(apr_status_t) apr_rmm_detach(apr_rmm_t *rmm)
{
/* A noop until we introduce locked/refcounts */
return APR_SUCCESS;
}
APU_DECLARE(apr_rmm_off_t) apr_rmm_malloc(apr_rmm_t *rmm, apr_size_t reqsize)
{
apr_rmm_off_t this;
reqsize = APR_ALIGN_DEFAULT(reqsize) + RMM_BLOCK_SIZE;
APR_ANYLOCK_LOCK(&rmm->lock);
this = find_block_of_size(rmm, reqsize);
if (this) {
move_block(rmm, this, 0);
this += RMM_BLOCK_SIZE;
}
APR_ANYLOCK_UNLOCK(&rmm->lock);
return this;
}
APU_DECLARE(apr_rmm_off_t) apr_rmm_calloc(apr_rmm_t *rmm, apr_size_t reqsize)
{
apr_rmm_off_t this;
reqsize = APR_ALIGN_DEFAULT(reqsize) + RMM_BLOCK_SIZE;
APR_ANYLOCK_LOCK(&rmm->lock);
this = find_block_of_size(rmm, reqsize);
if (this) {
move_block(rmm, this, 0);
this += RMM_BLOCK_SIZE;
memset((char*)rmm->base + this, 0, reqsize - RMM_BLOCK_SIZE);
}
APR_ANYLOCK_UNLOCK(&rmm->lock);
return this;
}
APU_DECLARE(apr_rmm_off_t) apr_rmm_realloc(apr_rmm_t *rmm, void *entity,
apr_size_t reqsize)
{
apr_rmm_off_t this;
apr_rmm_off_t old;
struct rmm_block_t *blk;
apr_size_t oldsize;
if (!entity) {
return apr_rmm_malloc(rmm, reqsize);
}
reqsize = APR_ALIGN_DEFAULT(reqsize);
old = apr_rmm_offset_get(rmm, entity);
if ((this = apr_rmm_malloc(rmm, reqsize)) == 0) {
return 0;
}
blk = (rmm_block_t*)((char*)rmm->base + old - RMM_BLOCK_SIZE);
oldsize = blk->size;
memcpy(apr_rmm_addr_get(rmm, this),
apr_rmm_addr_get(rmm, old), oldsize < reqsize ? oldsize : reqsize);
apr_rmm_free(rmm, old);
return this;
}
APU_DECLARE(apr_status_t) apr_rmm_free(apr_rmm_t *rmm, apr_rmm_off_t this)
{
apr_status_t rv;
struct rmm_block_t *blk;
/* A little sanity check is always healthy, especially here.
* If we really cared, we could make this compile-time
*/
if (this < RMM_HDR_BLOCK_SIZE + RMM_BLOCK_SIZE) {
return APR_EINVAL;
}
this -= RMM_BLOCK_SIZE;
blk = (rmm_block_t*)((char*)rmm->base + this);
if ((rv = APR_ANYLOCK_LOCK(&rmm->lock)) != APR_SUCCESS) {
return rv;
}
if (blk->prev) {
struct rmm_block_t *prev = (rmm_block_t*)((char*)rmm->base + blk->prev);
if (prev->next != this) {
APR_ANYLOCK_UNLOCK(&rmm->lock);
return APR_EINVAL;
}
}
else {
if (rmm->base->firstused != this) {
APR_ANYLOCK_UNLOCK(&rmm->lock);
return APR_EINVAL;
}
}
if (blk->next) {
struct rmm_block_t *next = (rmm_block_t*)((char*)rmm->base + blk->next);
if (next->prev != this) {
APR_ANYLOCK_UNLOCK(&rmm->lock);
return APR_EINVAL;
}
}
/* Ok, it remained [apparently] sane, so unlink it
*/
move_block(rmm, this, 1);
return APR_ANYLOCK_UNLOCK(&rmm->lock);
}
APU_DECLARE(void *) apr_rmm_addr_get(apr_rmm_t *rmm, apr_rmm_off_t entity)
{
/* debug-sanity checking here would be good
*/
return (void*)((char*)rmm->base + entity);
}
APU_DECLARE(apr_rmm_off_t) apr_rmm_offset_get(apr_rmm_t *rmm, void* entity)
{
/* debug, or always, sanity checking here would be good
* since the primitive is apr_rmm_off_t, I don't mind penalizing
* inverse conversions for safety, unless someone can prove that
* there is no choice in some cases.
*/
return ((char*)entity - (char*)rmm->base);
}
APU_DECLARE(apr_size_t) apr_rmm_overhead_get(int n)
{
/* overhead per block is at most APR_ALIGN_DEFAULT(1) wasted bytes
* for alignment overhead, plus the size of the rmm_block_t
* structure. */
return RMM_HDR_BLOCK_SIZE + n * (RMM_BLOCK_SIZE + APR_ALIGN_DEFAULT(1));
}