pb_bufmgr_slab.c 14.4 KB
Newer Older
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32
/**************************************************************************
 *
 * 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.
 * 
33 34
 * @sa http://en.wikipedia.org/wiki/Slab_allocation
 * 
35 36 37 38 39
 * @author Thomas Hellstrom <thomas-at-tungstengraphics-dot-com>
 * @author Jose Fonseca <jrfonseca@tungstengraphics.com>
 */

#include "pipe/p_compiler.h"
40
#include "util/u_debug.h"
41
#include "os/os_thread.h"
42
#include "pipe/p_defines.h"
43
#include "util/u_memory.h"
44 45 46 47 48 49 50 51 52
#include "util/u_double_list.h"
#include "util/u_time.h"

#include "pb_buffer.h"
#include "pb_bufmgr.h"


struct pb_slab;

53 54 55 56 57 58

/**
 * Buffer in a slab.
 * 
 * Sub-allocation of a contiguous buffer.
 */
59 60 61 62 63
struct pb_slab_buffer
{
   struct pb_buffer base;
   
   struct pb_slab *slab;
64
   
65
   struct list_head head;
66
   
67
   unsigned mapCount;
68 69
   
   /** Offset relative to the start of the slab buffer. */
70
   pb_size start;
71 72 73
   
   /** Use when validating, to signal that all mappings are finished */
   /* TODO: Actually validation does not reach this stage yet */
74
   pipe_condvar event;
75 76
};

77 78 79 80

/**
 * Slab -- a contiguous piece of memory. 
 */
81 82 83 84
struct pb_slab
{
   struct list_head head;
   struct list_head freeBuffers;
85 86
   pb_size numBuffers;
   pb_size numFree;
87
   
88
   struct pb_slab_buffer *buffers;
89
   struct pb_slab_manager *mgr;
90
   
91
   /** Buffer from the provider */
92
   struct pb_buffer *bo;
93
   
94 95 96
   void *virtual;   
};

97 98 99 100 101

/**
 * It adds/removes slabs as needed in order to meet the allocation/destruction 
 * of individual buffers.
 */
102
struct pb_slab_manager 
103
{
104 105
   struct pb_manager base;
   
106
   /** From where we get our buffers */
107
   struct pb_manager *provider;
108 109
   
   /** Size of the buffers we hand on downstream */
110
   pb_size bufSize;
111 112
   
   /** Size of the buffers we request upstream */
113
   pb_size slabSize;
114 115 116 117 118 119 120
   
   /** 
    * Alignment, usage to be used to allocate the slab buffers.
    * 
    * We can only provide buffers which are consistent (in alignment, usage) 
    * with this description.   
    */
121 122
   struct pb_desc desc;

123 124 125 126 127 128
   /** 
    * Partial slabs
    * 
    * Full slabs are not stored in any list. Empty slabs are destroyed 
    * immediatly.
    */
129
   struct list_head slabs;
130
   
131
   pipe_mutex mutex;
132 133
};

134

135
/**
136 137 138 139 140 141 142
 * 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.
 * 
143 144 145
 * The data of this structure remains constant after
 * initialization and thus needs no mutex protection.
 */
146
struct pb_slab_range_manager 
147 148 149
{
   struct pb_manager base;

150
   struct pb_manager *provider;
151
   
152 153
   pb_size minBufSize;
   pb_size maxBufSize;
154 155
   
   /** @sa pb_slab_manager::desc */ 
156
   struct pb_desc desc;
157 158
   
   unsigned numBuckets;
159
   pb_size *bucketSizes;
160 161
   
   /** Array of pb_slab_manager, one for each bucket size */
162
   struct pb_manager **buckets;
163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181
};


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


182 183 184 185 186 187 188 189
static INLINE struct pb_slab_range_manager *
pb_slab_range_manager(struct pb_manager *mgr)
{
   assert(mgr);
   return (struct pb_slab_range_manager *)mgr;
}


190
/**
191
 * Delete a buffer from the slab delayed list and put
192 193 194 195 196 197 198
 * 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;
199
   struct pb_slab_manager *mgr = slab->mgr;
200 201
   struct list_head *list = &buf->head;

202
   pipe_mutex_lock(mgr->mutex);
203
   
204
   assert(!pipe_is_referenced(&buf->base.base.reference));
205 206 207 208 209 210 211 212
   
   buf->mapCount = 0;

   LIST_DEL(list);
   LIST_ADDTAIL(list, &slab->freeBuffers);
   slab->numFree++;

   if (slab->head.next == &slab->head)
213
      LIST_ADDTAIL(&slab->head, &mgr->slabs);
214

215
   /* If the slab becomes totally empty, free it */
216 217
   if (slab->numFree == slab->numBuffers) {
      list = &slab->head;
218 219 220 221
      LIST_DELINIT(list);
      pb_reference(&slab->bo, NULL);
      FREE(slab->buffers);
      FREE(slab);
222 223
   }

224
   pipe_mutex_unlock(mgr->mutex);
225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245
}


static void *
pb_slab_buffer_map(struct pb_buffer *_buf, 
                   unsigned flags)
{
   struct pb_slab_buffer *buf = pb_slab_buffer(_buf);

   ++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) 
246
       pipe_condvar_broadcast(buf->event);
247 248 249
}


250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268
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);
}


269 270 271
static void
pb_slab_buffer_get_base_buffer(struct pb_buffer *_buf,
                               struct pb_buffer **base_buf,
272
                               pb_size *offset)
273 274 275 276 277 278 279 280 281 282 283 284
{
   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,
285 286
      pb_slab_buffer_validate,
      pb_slab_buffer_fence,
287 288 289 290
      pb_slab_buffer_get_base_buffer
};


291 292 293 294 295
/**
 * Create a new slab.
 * 
 * Called when we ran out of free slabs.
 */
296
static enum pipe_error
297
pb_slab_create(struct pb_slab_manager *mgr)
298 299 300
{
   struct pb_slab *slab;
   struct pb_slab_buffer *buf;
301
   unsigned numBuffers;
302
   unsigned i;
303
   enum pipe_error ret;
304 305 306 307 308

   slab = CALLOC_STRUCT(pb_slab);
   if (!slab)
      return PIPE_ERROR_OUT_OF_MEMORY;

309 310 311
   slab->bo = mgr->provider->create_buffer(mgr->provider, mgr->slabSize, &mgr->desc);
   if(!slab->bo) {
      ret = PIPE_ERROR_OUT_OF_MEMORY;
312
      goto out_err0;
313
   }
314

315 316
   /* Note down the slab virtual address. All mappings are accessed directly 
    * through this address so it is required that the buffer is pinned. */
317
   slab->virtual = pb_map(slab->bo, 
Keith Whitwell's avatar
Keith Whitwell committed
318 319
                          PB_USAGE_CPU_READ |
                          PB_USAGE_CPU_WRITE);
320 321
   if(!slab->virtual) {
      ret = PIPE_ERROR_OUT_OF_MEMORY;
322
      goto out_err1;
323
   }
324 325
   pb_unmap(slab->bo);

326
   numBuffers = slab->bo->base.size / mgr->bufSize;
327 328 329 330 331 332 333 334 335 336 337

   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;
338
   slab->mgr = mgr;
339 340 341

   buf = slab->buffers;
   for (i=0; i < numBuffers; ++i) {
342
      pipe_reference_init(&buf->base.base.reference, 0);
343
      buf->base.base.size = mgr->bufSize;
344 345 346 347
      buf->base.base.alignment = 0;
      buf->base.base.usage = 0;
      buf->base.vtbl = &pb_slab_buffer_vtbl;
      buf->slab = slab;
348
      buf->start = i* mgr->bufSize;
349
      buf->mapCount = 0;
350
      pipe_condvar_init(buf->event);
351 352 353 354 355
      LIST_ADDTAIL(&buf->head, &slab->freeBuffers);
      slab->numFree++;
      buf++;
   }

356
   /* Add this slab to the list of partial slabs */
357
   LIST_ADDTAIL(&slab->head, &mgr->slabs);
358 359 360 361 362 363 364 365 366 367 368 369

   return PIPE_OK;

out_err1: 
   pb_reference(&slab->bo, NULL);
out_err0: 
   FREE(slab);
   return ret;
}


static struct pb_buffer *
370
pb_slab_manager_create_buffer(struct pb_manager *_mgr,
371
                              pb_size size,
372 373
                              const struct pb_desc *desc)
{
374
   struct pb_slab_manager *mgr = pb_slab_manager(_mgr);
375 376 377 378
   static struct pb_slab_buffer *buf;
   struct pb_slab *slab;
   struct list_head *list;

379
   /* check size */
380 381
   assert(size <= mgr->bufSize);
   if(size > mgr->bufSize)
382 383 384
      return NULL;
   
   /* check if we can provide the requested alignment */
385 386
   assert(pb_check_alignment(desc->alignment, mgr->desc.alignment));
   if(!pb_check_alignment(desc->alignment, mgr->desc.alignment))
387
      return NULL;
388 389
   assert(pb_check_alignment(desc->alignment, mgr->bufSize));
   if(!pb_check_alignment(desc->alignment, mgr->bufSize))
390
      return NULL;
391

392 393 394 395
   assert(pb_check_usage(desc->usage, mgr->desc.usage));
   if(!pb_check_usage(desc->usage, mgr->desc.usage))
      return NULL;

396
   pipe_mutex_lock(mgr->mutex);
397 398
   
   /* Create a new slab, if we run out of partial slabs */
399
   if (mgr->slabs.next == &mgr->slabs) {
400
      (void) pb_slab_create(mgr);
401
      if (mgr->slabs.next == &mgr->slabs) {
402
	 pipe_mutex_unlock(mgr->mutex);
403 404
	 return NULL;
      }
405
   }
406 407
   
   /* Allocate the buffer from a partial (or just created) slab */
408
   list = mgr->slabs.next;
409
   slab = LIST_ENTRY(struct pb_slab, list, head);
410 411
   
   /* If totally full remove from the partial slab list */
412 413 414 415 416 417
   if (--slab->numFree == 0)
      LIST_DELINIT(list);

   list = slab->freeBuffers.next;
   LIST_DELINIT(list);

418
   pipe_mutex_unlock(mgr->mutex);
419
   buf = LIST_ENTRY(struct pb_slab_buffer, list, head);
420
   
421
   pipe_reference_init(&buf->base.base.reference, 1);
422 423 424
   buf->base.base.alignment = desc->alignment;
   buf->base.base.usage = desc->usage;
   
425 426 427 428
   return &buf->base;
}


429 430 431 432 433 434 435 436 437 438 439
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);
}


440
static void
441
pb_slab_manager_destroy(struct pb_manager *_mgr)
442
{
443
   struct pb_slab_manager *mgr = pb_slab_manager(_mgr);
444

445 446
   /* TODO: cleanup all allocated buffers */
   FREE(mgr);
447 448 449 450
}


struct pb_manager *
451
pb_slab_manager_create(struct pb_manager *provider,
452 453
                       pb_size bufSize,
                       pb_size slabSize,
454 455 456 457 458 459 460 461 462 463
                       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;
464
   mgr->base.flush = pb_slab_manager_flush;
465 466 467 468 469 470 471 472

   mgr->provider = provider;
   mgr->bufSize = bufSize;
   mgr->slabSize = slabSize;
   mgr->desc = *desc;

   LIST_INITHEAD(&mgr->slabs);
   
473
   pipe_mutex_init(mgr->mutex);
474 475 476 477 478 479 480

   return &mgr->base;
}


static struct pb_buffer *
pb_slab_range_manager_create_buffer(struct pb_manager *_mgr,
481
                                    pb_size size,
482
                                    const struct pb_desc *desc)
483
{
484
   struct pb_slab_range_manager *mgr = pb_slab_range_manager(_mgr);
485
   pb_size bufSize;
486
   pb_size reqSize = size;
487
   unsigned i;
488

489 490 491
   if(desc->alignment > reqSize)
	   reqSize = desc->alignment;

492 493
   bufSize = mgr->minBufSize;
   for (i = 0; i < mgr->numBuckets; ++i) {
494
      if(bufSize >= reqSize)
495 496 497 498 499 500 501 502 503
	 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);
}


504 505 506 507 508 509 510 511 512 513 514 515 516
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);
}


517 518 519 520 521 522 523 524 525 526 527 528 529 530 531 532
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,
533 534 535
                             pb_size minBufSize,
                             pb_size maxBufSize,
                             pb_size slabSize,
536 537 538
                             const struct pb_desc *desc)
{
   struct pb_slab_range_manager *mgr;
539
   pb_size bufSize;
540 541
   unsigned i;

542 543 544
   if(!provider)
      return NULL;
   
545 546
   mgr = CALLOC_STRUCT(pb_slab_range_manager);
   if (!mgr)
547 548
      goto out_err0;

549 550
   mgr->base.destroy = pb_slab_range_manager_destroy;
   mgr->base.create_buffer = pb_slab_range_manager_create_buffer;
551
   mgr->base.flush = pb_slab_range_manager_flush;
552

553 554 555 556 557 558 559 560 561
   mgr->provider = provider;
   mgr->minBufSize = minBufSize;
   mgr->maxBufSize = maxBufSize;

   mgr->numBuckets = 1;
   bufSize = minBufSize;
   while(bufSize < maxBufSize) {
      bufSize *= 2;
      ++mgr->numBuckets;
562
   }
563 564 565 566
   
   mgr->buckets = CALLOC(mgr->numBuckets, sizeof(*mgr->buckets));
   if (!mgr->buckets)
      goto out_err1;
567

568 569 570 571 572 573 574
   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;
   }
575

576
   return &mgr->base;
577 578

out_err2: 
579 580 581 582
   for (i = 0; i < mgr->numBuckets; ++i)
      if(mgr->buckets[i])
	    mgr->buckets[i]->destroy(mgr->buckets[i]);
   FREE(mgr->buckets);
583
out_err1: 
584
   FREE(mgr);
585 586 587
out_err0:
   return NULL;
}