Subversion Repositories Kolibri OS

/**************************************************************************

 *

 * 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 

 * @author Jose Fonseca 

 */

#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)

{

   assert(buf);

   return (struct pb_slab_buffer *)buf;

}

static INLINE struct pb_slab_manager *

pb_slab_manager(struct pb_manager *mgr)

{

   assert(mgr);

   return (struct pb_slab_manager *)mgr;

}

static INLINE struct pb_slab_range_manager *

pb_slab_range_manager(struct pb_manager *mgr)

{

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

   assert(size <= mgr->bufSize);

   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);

   assert(mgr->provider->flush);

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

   assert(mgr->provider->flush);

   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;

}