/**************************************************************************
*
* Copyright 2006-2008 Tungsten Graphics, Inc., Cedar Park, TX., USA
* All Rights Reserved.
*
* Permission is hereby granted, FREE of charge, to any person obtaining a
* copy of this software and associated documentation files (the
* "Software"), to deal in the Software without restriction, including
* without limitation the rights to use, copy, modify, merge, publish,
* distribute, sub license, and/or sell copies of the Software, and to
* permit persons to whom the Software is furnished to do so, subject to
* the following conditions:
*
* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
* IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
* FITNESS FOR A PARTICULAR PURPOSE AND NON-INFRINGEMENT. IN NO EVENT SHALL
* THE COPYRIGHT HOLDERS, AUTHORS AND/OR ITS SUPPLIERS BE LIABLE FOR ANY CLAIM,
* DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR
* OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE
* USE OR OTHER DEALINGS IN THE SOFTWARE.
*
* The above copyright notice and this permission notice (including the
* next paragraph) shall be included in all copies or substantial portions
* of the Software.
*
*
**************************************************************************/
/**
* @file
* S-lab pool implementation.
*
* @sa http://en.wikipedia.org/wiki/Slab_allocation
*
* @author Thomas Hellstrom <thomas-at-tungstengraphics-dot-com>
* @author Jose Fonseca <jrfonseca@tungstengraphics.com>
*/
#include "pipe/p_compiler.h"
#include "util/u_debug.h"
#include "os/os_thread.h"
#include "pipe/p_defines.h"
#include "util/u_memory.h"
#include "util/u_double_list.h"
#include "util/u_time.h"
#include "pb_buffer.h"
#include "pb_bufmgr.h"
struct pb_slab;
/**
* Buffer in a slab.
*
* Sub-allocation of a contiguous buffer.
*/
struct pb_slab_buffer
{
struct pb_buffer base;
struct pb_slab *slab;
struct list_head head;
unsigned mapCount;
/** Offset relative to the start of the slab buffer. */
pb_size start;
/** Use when validating, to signal that all mappings are finished */
/* TODO: Actually validation does not reach this stage yet */
pipe_condvar event;
};
/**
* Slab -- a contiguous piece of memory.
*/
struct pb_slab
{
struct list_head head;
struct list_head freeBuffers;
pb_size numBuffers;
pb_size numFree;
struct pb_slab_buffer *buffers;
struct pb_slab_manager *mgr;
/** Buffer from the provider */
struct pb_buffer *bo;
void *virtual;
};
/**
* It adds/removes slabs as needed in order to meet the allocation/destruction
* of individual buffers.
*/
struct pb_slab_manager
{
struct pb_manager base;
/** From where we get our buffers */
struct pb_manager *provider;
/** Size of the buffers we hand on downstream */
pb_size bufSize;
/** Size of the buffers we request upstream */
pb_size slabSize;
/**
* Alignment, usage to be used to allocate the slab buffers.
*
* We can only provide buffers which are consistent (in alignment, usage)
* with this description.
*/
struct pb_desc desc;
/**
* Partial slabs
*
* Full slabs are not stored in any list. Empty slabs are destroyed
* immediatly.
*/
struct list_head slabs;
pipe_mutex mutex;
};
/**
* Wrapper around several slabs, therefore capable of handling buffers of
* multiple sizes.
*
* This buffer manager just dispatches buffer allocations to the appropriate slab
* manager, according to the requested buffer size, or by passes the slab
* managers altogether for even greater sizes.
*
* The data of this structure remains constant after
* initialization and thus needs no mutex protection.
*/
struct pb_slab_range_manager
{
struct pb_manager base;
struct pb_manager *provider;
pb_size minBufSize;
pb_size maxBufSize;
/** @sa pb_slab_manager::desc */
struct pb_desc desc;
unsigned numBuckets;
pb_size *bucketSizes;
/** Array of pb_slab_manager, one for each bucket size */
struct pb_manager **buckets;
};
static INLINE struct pb_slab_buffer *
pb_slab_buffer(struct pb_buffer *buf)
{
return (struct pb_slab_buffer *)buf;
}
static INLINE struct pb_slab_manager *
pb_slab_manager(struct pb_manager *mgr)
{
return (struct pb_slab_manager *)mgr;
}
static INLINE struct pb_slab_range_manager *
pb_slab_range_manager(struct pb_manager *mgr)
{
return (struct pb_slab_range_manager *)mgr;
}
/**
* Delete a buffer from the slab delayed list and put
* it on the slab FREE list.
*/
static void
pb_slab_buffer_destroy(struct pb_buffer *_buf)
{
struct pb_slab_buffer *buf = pb_slab_buffer(_buf);
struct pb_slab *slab = buf->slab;
struct pb_slab_manager *mgr = slab->mgr;
struct list_head *list = &buf->head;
pipe_mutex_lock(mgr->mutex);
assert(!pipe_is_referenced
(&buf
->base.
reference));
buf->mapCount = 0;
LIST_DEL(list);
LIST_ADDTAIL(list, &slab->freeBuffers);
slab->numFree++;
if (slab->head.next == &slab->head)
LIST_ADDTAIL(&slab->head, &mgr->slabs);
/* If the slab becomes totally empty, free it */
if (slab->numFree == slab->numBuffers) {
list = &slab->head;
LIST_DELINIT(list);
pb_reference(&slab->bo, NULL);
FREE(slab->buffers);
FREE(slab);
}
pipe_mutex_unlock(mgr->mutex);
}
static void *
pb_slab_buffer_map(struct pb_buffer *_buf,
unsigned flags,
void *flush_ctx)
{
struct pb_slab_buffer *buf = pb_slab_buffer(_buf);
/* XXX: it will be necessary to remap here to propagate flush_ctx */
++buf->mapCount;
return (void *) ((uint8_t *) buf->slab->virtual + buf->start);
}
static void
pb_slab_buffer_unmap(struct pb_buffer *_buf)
{
struct pb_slab_buffer *buf = pb_slab_buffer(_buf);
--buf->mapCount;
if (buf->mapCount == 0)
pipe_condvar_broadcast(buf->event);
}
static enum pipe_error
pb_slab_buffer_validate(struct pb_buffer *_buf,
struct pb_validate *vl,
unsigned flags)
{
struct pb_slab_buffer *buf = pb_slab_buffer(_buf);
return pb_validate(buf->slab->bo, vl, flags);
}
static void
pb_slab_buffer_fence(struct pb_buffer *_buf,
struct pipe_fence_handle *fence)
{
struct pb_slab_buffer *buf = pb_slab_buffer(_buf);
pb_fence(buf->slab->bo, fence);
}
static void
pb_slab_buffer_get_base_buffer(struct pb_buffer *_buf,
struct pb_buffer **base_buf,
pb_size *offset)
{
struct pb_slab_buffer *buf = pb_slab_buffer(_buf);
pb_get_base_buffer(buf->slab->bo, base_buf, offset);
*offset += buf->start;
}
static const struct pb_vtbl
pb_slab_buffer_vtbl = {
pb_slab_buffer_destroy,
pb_slab_buffer_map,
pb_slab_buffer_unmap,
pb_slab_buffer_validate,
pb_slab_buffer_fence,
pb_slab_buffer_get_base_buffer
};
/**
* Create a new slab.
*
* Called when we ran out of free slabs.
*/
static enum pipe_error
pb_slab_create(struct pb_slab_manager *mgr)
{
struct pb_slab *slab;
struct pb_slab_buffer *buf;
unsigned numBuffers;
unsigned i;
enum pipe_error ret;
slab = CALLOC_STRUCT(pb_slab);
if (!slab)
return PIPE_ERROR_OUT_OF_MEMORY;
slab->bo = mgr->provider->create_buffer(mgr->provider, mgr->slabSize, &mgr->desc);
if(!slab->bo) {
ret = PIPE_ERROR_OUT_OF_MEMORY;
goto out_err0;
}
/* Note down the slab virtual address. All mappings are accessed directly
* through this address so it is required that the buffer is pinned. */
slab->virtual = pb_map(slab->bo,
PB_USAGE_CPU_READ |
PB_USAGE_CPU_WRITE, NULL);
if(!slab->virtual) {
ret = PIPE_ERROR_OUT_OF_MEMORY;
goto out_err1;
}
pb_unmap(slab->bo);
numBuffers = slab->bo->size / mgr->bufSize;
slab->buffers = CALLOC(numBuffers, sizeof(*slab->buffers));
if (!slab->buffers) {
ret = PIPE_ERROR_OUT_OF_MEMORY;
goto out_err1;
}
LIST_INITHEAD(&slab->head);
LIST_INITHEAD(&slab->freeBuffers);
slab->numBuffers = numBuffers;
slab->numFree = 0;
slab->mgr = mgr;
buf = slab->buffers;
for (i=0; i < numBuffers; ++i) {
pipe_reference_init(&buf->base.reference, 0);
buf->base.size = mgr->bufSize;
buf->base.alignment = 0;
buf->base.usage = 0;
buf->base.vtbl = &pb_slab_buffer_vtbl;
buf->slab = slab;
buf->start = i* mgr->bufSize;
buf->mapCount = 0;
pipe_condvar_init(buf->event);
LIST_ADDTAIL(&buf->head, &slab->freeBuffers);
slab->numFree++;
buf++;
}
/* Add this slab to the list of partial slabs */
LIST_ADDTAIL(&slab->head, &mgr->slabs);
return PIPE_OK;
out_err1:
pb_reference(&slab->bo, NULL);
out_err0:
FREE(slab);
return ret;
}
static struct pb_buffer *
pb_slab_manager_create_buffer(struct pb_manager *_mgr,
pb_size size,
const struct pb_desc *desc)
{
struct pb_slab_manager *mgr = pb_slab_manager(_mgr);
static struct pb_slab_buffer *buf;
struct pb_slab *slab;
struct list_head *list;
/* check size */
if(size > mgr->bufSize)
return NULL;
/* check if we can provide the requested alignment */
assert(pb_check_alignment
(desc
->alignment
, mgr
->desc.
alignment)); if(!pb_check_alignment(desc->alignment, mgr->desc.alignment))
return NULL;
assert(pb_check_alignment
(desc
->alignment
, mgr
->bufSize
)); if(!pb_check_alignment(desc->alignment, mgr->bufSize))
return NULL;
assert(pb_check_usage
(desc
->usage
, mgr
->desc.
usage)); if(!pb_check_usage(desc->usage, mgr->desc.usage))
return NULL;
pipe_mutex_lock(mgr->mutex);
/* Create a new slab, if we run out of partial slabs */
if (mgr->slabs.next == &mgr->slabs) {
(void) pb_slab_create(mgr);
if (mgr->slabs.next == &mgr->slabs) {
pipe_mutex_unlock(mgr->mutex);
return NULL;
}
}
/* Allocate the buffer from a partial (or just created) slab */
list = mgr->slabs.next;
slab = LIST_ENTRY(struct pb_slab, list, head);
/* If totally full remove from the partial slab list */
if (--slab->numFree == 0)
LIST_DELINIT(list);
list = slab->freeBuffers.next;
LIST_DELINIT(list);
pipe_mutex_unlock(mgr->mutex);
buf = LIST_ENTRY(struct pb_slab_buffer, list, head);
pipe_reference_init(&buf->base.reference, 1);
buf->base.alignment = desc->alignment;
buf->base.usage = desc->usage;
return &buf->base;
}
static void
pb_slab_manager_flush(struct pb_manager *_mgr)
{
struct pb_slab_manager *mgr = pb_slab_manager(_mgr);
if(mgr->provider->flush)
mgr->provider->flush(mgr->provider);
}
static void
pb_slab_manager_destroy(struct pb_manager *_mgr)
{
struct pb_slab_manager *mgr = pb_slab_manager(_mgr);
/* TODO: cleanup all allocated buffers */
FREE(mgr);
}
struct pb_manager *
pb_slab_manager_create(struct pb_manager *provider,
pb_size bufSize,
pb_size slabSize,
const struct pb_desc *desc)
{
struct pb_slab_manager *mgr;
mgr = CALLOC_STRUCT(pb_slab_manager);
if (!mgr)
return NULL;
mgr->base.destroy = pb_slab_manager_destroy;
mgr->base.create_buffer = pb_slab_manager_create_buffer;
mgr->base.flush = pb_slab_manager_flush;
mgr->provider = provider;
mgr->bufSize = bufSize;
mgr->slabSize = slabSize;
mgr->desc = *desc;
LIST_INITHEAD(&mgr->slabs);
pipe_mutex_init(mgr->mutex);
return &mgr->base;
}
static struct pb_buffer *
pb_slab_range_manager_create_buffer(struct pb_manager *_mgr,
pb_size size,
const struct pb_desc *desc)
{
struct pb_slab_range_manager *mgr = pb_slab_range_manager(_mgr);
pb_size bufSize;
pb_size reqSize = size;
unsigned i;
if(desc->alignment > reqSize)
reqSize = desc->alignment;
bufSize = mgr->minBufSize;
for (i = 0; i < mgr->numBuckets; ++i) {
if(bufSize >= reqSize)
return mgr->buckets[i]->create_buffer(mgr->buckets[i], size, desc);
bufSize *= 2;
}
/* Fall back to allocate a buffer object directly from the provider. */
return mgr->provider->create_buffer(mgr->provider, size, desc);
}
static void
pb_slab_range_manager_flush(struct pb_manager *_mgr)
{
struct pb_slab_range_manager *mgr = pb_slab_range_manager(_mgr);
/* Individual slabs don't hold any temporary buffers so no need to call them */
if(mgr->provider->flush)
mgr->provider->flush(mgr->provider);
}
static void
pb_slab_range_manager_destroy(struct pb_manager *_mgr)
{
struct pb_slab_range_manager *mgr = pb_slab_range_manager(_mgr);
unsigned i;
for (i = 0; i < mgr->numBuckets; ++i)
mgr->buckets[i]->destroy(mgr->buckets[i]);
FREE(mgr->buckets);
FREE(mgr->bucketSizes);
FREE(mgr);
}
struct pb_manager *
pb_slab_range_manager_create(struct pb_manager *provider,
pb_size minBufSize,
pb_size maxBufSize,
pb_size slabSize,
const struct pb_desc *desc)
{
struct pb_slab_range_manager *mgr;
pb_size bufSize;
unsigned i;
if(!provider)
return NULL;
mgr = CALLOC_STRUCT(pb_slab_range_manager);
if (!mgr)
goto out_err0;
mgr->base.destroy = pb_slab_range_manager_destroy;
mgr->base.create_buffer = pb_slab_range_manager_create_buffer;
mgr->base.flush = pb_slab_range_manager_flush;
mgr->provider = provider;
mgr->minBufSize = minBufSize;
mgr->maxBufSize = maxBufSize;
mgr->numBuckets = 1;
bufSize = minBufSize;
while(bufSize < maxBufSize) {
bufSize *= 2;
++mgr->numBuckets;
}
mgr->buckets = CALLOC(mgr->numBuckets, sizeof(*mgr->buckets));
if (!mgr->buckets)
goto out_err1;
bufSize = minBufSize;
for (i = 0; i < mgr->numBuckets; ++i) {
mgr->buckets[i] = pb_slab_manager_create(provider, bufSize, slabSize, desc);
if(!mgr->buckets[i])
goto out_err2;
bufSize *= 2;
}
return &mgr->base;
out_err2:
for (i = 0; i < mgr->numBuckets; ++i)
if(mgr->buckets[i])
mgr->buckets[i]->destroy(mgr->buckets[i]);
FREE(mgr->buckets);
out_err1:
FREE(mgr);
out_err0:
return NULL;
}