OSDN Git Service

anv/pipeline: Add support for caching the push constant map
[android-x86/external-mesa.git] / src / intel / vulkan / anv_allocator.c
1 /*
2  * Copyright © 2015 Intel Corporation
3  *
4  * Permission is hereby granted, free of charge, to any person obtaining a
5  * copy of this software and associated documentation files (the "Software"),
6  * to deal in the Software without restriction, including without limitation
7  * the rights to use, copy, modify, merge, publish, distribute, sublicense,
8  * and/or sell copies of the Software, and to permit persons to whom the
9  * Software is furnished to do so, subject to the following conditions:
10  *
11  * The above copyright notice and this permission notice (including the next
12  * paragraph) shall be included in all copies or substantial portions of the
13  * Software.
14  *
15  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
16  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
17  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL
18  * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
19  * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
20  * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
21  * IN THE SOFTWARE.
22  */
23
24 #include <stdint.h>
25 #include <stdlib.h>
26 #include <unistd.h>
27 #include <values.h>
28 #include <assert.h>
29 #include <linux/futex.h>
30 #include <linux/memfd.h>
31 #include <sys/time.h>
32 #include <sys/mman.h>
33 #include <sys/syscall.h>
34
35 #include "anv_private.h"
36
37 #ifdef HAVE_VALGRIND
38 #define VG_NOACCESS_READ(__ptr) ({                       \
39    VALGRIND_MAKE_MEM_DEFINED((__ptr), sizeof(*(__ptr))); \
40    __typeof(*(__ptr)) __val = *(__ptr);                  \
41    VALGRIND_MAKE_MEM_NOACCESS((__ptr), sizeof(*(__ptr)));\
42    __val;                                                \
43 })
44 #define VG_NOACCESS_WRITE(__ptr, __val) ({                  \
45    VALGRIND_MAKE_MEM_UNDEFINED((__ptr), sizeof(*(__ptr)));  \
46    *(__ptr) = (__val);                                      \
47    VALGRIND_MAKE_MEM_NOACCESS((__ptr), sizeof(*(__ptr)));   \
48 })
49 #else
50 #define VG_NOACCESS_READ(__ptr) (*(__ptr))
51 #define VG_NOACCESS_WRITE(__ptr, __val) (*(__ptr) = (__val))
52 #endif
53
54 /* Design goals:
55  *
56  *  - Lock free (except when resizing underlying bos)
57  *
58  *  - Constant time allocation with typically only one atomic
59  *
60  *  - Multiple allocation sizes without fragmentation
61  *
62  *  - Can grow while keeping addresses and offset of contents stable
63  *
64  *  - All allocations within one bo so we can point one of the
65  *    STATE_BASE_ADDRESS pointers at it.
66  *
67  * The overall design is a two-level allocator: top level is a fixed size, big
68  * block (8k) allocator, which operates out of a bo.  Allocation is done by
69  * either pulling a block from the free list or growing the used range of the
70  * bo.  Growing the range may run out of space in the bo which we then need to
71  * grow.  Growing the bo is tricky in a multi-threaded, lockless environment:
72  * we need to keep all pointers and contents in the old map valid.  GEM bos in
73  * general can't grow, but we use a trick: we create a memfd and use ftruncate
74  * to grow it as necessary.  We mmap the new size and then create a gem bo for
75  * it using the new gem userptr ioctl.  Without heavy-handed locking around
76  * our allocation fast-path, there isn't really a way to munmap the old mmap,
77  * so we just keep it around until garbage collection time.  While the block
78  * allocator is lockless for normal operations, we block other threads trying
79  * to allocate while we're growing the map.  It sholdn't happen often, and
80  * growing is fast anyway.
81  *
82  * At the next level we can use various sub-allocators.  The state pool is a
83  * pool of smaller, fixed size objects, which operates much like the block
84  * pool.  It uses a free list for freeing objects, but when it runs out of
85  * space it just allocates a new block from the block pool.  This allocator is
86  * intended for longer lived state objects such as SURFACE_STATE and most
87  * other persistent state objects in the API.  We may need to track more info
88  * with these object and a pointer back to the CPU object (eg VkImage).  In
89  * those cases we just allocate a slightly bigger object and put the extra
90  * state after the GPU state object.
91  *
92  * The state stream allocator works similar to how the i965 DRI driver streams
93  * all its state.  Even with Vulkan, we need to emit transient state (whether
94  * surface state base or dynamic state base), and for that we can just get a
95  * block and fill it up.  These cases are local to a command buffer and the
96  * sub-allocator need not be thread safe.  The streaming allocator gets a new
97  * block when it runs out of space and chains them together so they can be
98  * easily freed.
99  */
100
101 /* Allocations are always at least 64 byte aligned, so 1 is an invalid value.
102  * We use it to indicate the free list is empty. */
103 #define EMPTY 1
104
105 struct anv_mmap_cleanup {
106    void *map;
107    size_t size;
108    uint32_t gem_handle;
109 };
110
111 #define ANV_MMAP_CLEANUP_INIT ((struct anv_mmap_cleanup){0})
112
113 static inline long
114 sys_futex(void *addr1, int op, int val1,
115           struct timespec *timeout, void *addr2, int val3)
116 {
117    return syscall(SYS_futex, addr1, op, val1, timeout, addr2, val3);
118 }
119
120 static inline int
121 futex_wake(uint32_t *addr, int count)
122 {
123    return sys_futex(addr, FUTEX_WAKE, count, NULL, NULL, 0);
124 }
125
126 static inline int
127 futex_wait(uint32_t *addr, int32_t value)
128 {
129    return sys_futex(addr, FUTEX_WAIT, value, NULL, NULL, 0);
130 }
131
132 static inline int
133 memfd_create(const char *name, unsigned int flags)
134 {
135    return syscall(SYS_memfd_create, name, flags);
136 }
137
138 static inline uint32_t
139 ilog2_round_up(uint32_t value)
140 {
141    assert(value != 0);
142    return 32 - __builtin_clz(value - 1);
143 }
144
145 static inline uint32_t
146 round_to_power_of_two(uint32_t value)
147 {
148    return 1 << ilog2_round_up(value);
149 }
150
151 static bool
152 anv_free_list_pop(union anv_free_list *list, void **map, int32_t *offset)
153 {
154    union anv_free_list current, new, old;
155
156    current.u64 = list->u64;
157    while (current.offset != EMPTY) {
158       /* We have to add a memory barrier here so that the list head (and
159        * offset) gets read before we read the map pointer.  This way we
160        * know that the map pointer is valid for the given offset at the
161        * point where we read it.
162        */
163       __sync_synchronize();
164
165       int32_t *next_ptr = *map + current.offset;
166       new.offset = VG_NOACCESS_READ(next_ptr);
167       new.count = current.count + 1;
168       old.u64 = __sync_val_compare_and_swap(&list->u64, current.u64, new.u64);
169       if (old.u64 == current.u64) {
170          *offset = current.offset;
171          return true;
172       }
173       current = old;
174    }
175
176    return false;
177 }
178
179 static void
180 anv_free_list_push(union anv_free_list *list, void *map, int32_t offset)
181 {
182    union anv_free_list current, old, new;
183    int32_t *next_ptr = map + offset;
184
185    old = *list;
186    do {
187       current = old;
188       VG_NOACCESS_WRITE(next_ptr, current.offset);
189       new.offset = offset;
190       new.count = current.count + 1;
191       old.u64 = __sync_val_compare_and_swap(&list->u64, current.u64, new.u64);
192    } while (old.u64 != current.u64);
193 }
194
195 /* All pointers in the ptr_free_list are assumed to be page-aligned.  This
196  * means that the bottom 12 bits should all be zero.
197  */
198 #define PFL_COUNT(x) ((uintptr_t)(x) & 0xfff)
199 #define PFL_PTR(x) ((void *)((uintptr_t)(x) & ~(uintptr_t)0xfff))
200 #define PFL_PACK(ptr, count) ({           \
201    (void *)(((uintptr_t)(ptr) & ~(uintptr_t)0xfff) | ((count) & 0xfff)); \
202 })
203
204 static bool
205 anv_ptr_free_list_pop(void **list, void **elem)
206 {
207    void *current = *list;
208    while (PFL_PTR(current) != NULL) {
209       void **next_ptr = PFL_PTR(current);
210       void *new_ptr = VG_NOACCESS_READ(next_ptr);
211       unsigned new_count = PFL_COUNT(current) + 1;
212       void *new = PFL_PACK(new_ptr, new_count);
213       void *old = __sync_val_compare_and_swap(list, current, new);
214       if (old == current) {
215          *elem = PFL_PTR(current);
216          return true;
217       }
218       current = old;
219    }
220
221    return false;
222 }
223
224 static void
225 anv_ptr_free_list_push(void **list, void *elem)
226 {
227    void *old, *current;
228    void **next_ptr = elem;
229
230    /* The pointer-based free list requires that the pointer be
231     * page-aligned.  This is because we use the bottom 12 bits of the
232     * pointer to store a counter to solve the ABA concurrency problem.
233     */
234    assert(((uintptr_t)elem & 0xfff) == 0);
235
236    old = *list;
237    do {
238       current = old;
239       VG_NOACCESS_WRITE(next_ptr, PFL_PTR(current));
240       unsigned new_count = PFL_COUNT(current) + 1;
241       void *new = PFL_PACK(elem, new_count);
242       old = __sync_val_compare_and_swap(list, current, new);
243    } while (old != current);
244 }
245
246 static uint32_t
247 anv_block_pool_grow(struct anv_block_pool *pool, struct anv_block_state *state);
248
249 void
250 anv_block_pool_init(struct anv_block_pool *pool,
251                     struct anv_device *device, uint32_t block_size)
252 {
253    assert(util_is_power_of_two(block_size));
254
255    pool->device = device;
256    pool->bo.gem_handle = 0;
257    pool->bo.offset = 0;
258    pool->bo.size = 0;
259    pool->bo.is_winsys_bo = false;
260    pool->block_size = block_size;
261    pool->free_list = ANV_FREE_LIST_EMPTY;
262    pool->back_free_list = ANV_FREE_LIST_EMPTY;
263
264    pool->fd = memfd_create("block pool", MFD_CLOEXEC);
265    if (pool->fd == -1)
266       return;
267
268    /* Just make it 2GB up-front.  The Linux kernel won't actually back it
269     * with pages until we either map and fault on one of them or we use
270     * userptr and send a chunk of it off to the GPU.
271     */
272    if (ftruncate(pool->fd, BLOCK_POOL_MEMFD_SIZE) == -1)
273       return;
274
275    anv_vector_init(&pool->mmap_cleanups,
276                    round_to_power_of_two(sizeof(struct anv_mmap_cleanup)), 128);
277
278    pool->state.next = 0;
279    pool->state.end = 0;
280    pool->back_state.next = 0;
281    pool->back_state.end = 0;
282
283    /* Immediately grow the pool so we'll have a backing bo. */
284    pool->state.end = anv_block_pool_grow(pool, &pool->state);
285 }
286
287 void
288 anv_block_pool_finish(struct anv_block_pool *pool)
289 {
290    struct anv_mmap_cleanup *cleanup;
291
292    anv_vector_foreach(cleanup, &pool->mmap_cleanups) {
293       if (cleanup->map)
294          munmap(cleanup->map, cleanup->size);
295       if (cleanup->gem_handle)
296          anv_gem_close(pool->device, cleanup->gem_handle);
297    }
298
299    anv_vector_finish(&pool->mmap_cleanups);
300
301    close(pool->fd);
302 }
303
304 #define PAGE_SIZE 4096
305
306 /** Grows and re-centers the block pool.
307  *
308  * We grow the block pool in one or both directions in such a way that the
309  * following conditions are met:
310  *
311  *  1) The size of the entire pool is always a power of two.
312  *
313  *  2) The pool only grows on both ends.  Neither end can get
314  *     shortened.
315  *
316  *  3) At the end of the allocation, we have about twice as much space
317  *     allocated for each end as we have used.  This way the pool doesn't
318  *     grow too far in one direction or the other.
319  *
320  *  4) If the _alloc_back() has never been called, then the back portion of
321  *     the pool retains a size of zero.  (This makes it easier for users of
322  *     the block pool that only want a one-sided pool.)
323  *
324  *  5) We have enough space allocated for at least one more block in
325  *     whichever side `state` points to.
326  *
327  *  6) The center of the pool is always aligned to both the block_size of
328  *     the pool and a 4K CPU page.
329  */
330 static uint32_t
331 anv_block_pool_grow(struct anv_block_pool *pool, struct anv_block_state *state)
332 {
333    size_t size;
334    void *map;
335    uint32_t gem_handle;
336    struct anv_mmap_cleanup *cleanup;
337
338    pthread_mutex_lock(&pool->device->mutex);
339
340    assert(state == &pool->state || state == &pool->back_state);
341
342    /* Gather a little usage information on the pool.  Since we may have
343     * threadsd waiting in queue to get some storage while we resize, it's
344     * actually possible that total_used will be larger than old_size.  In
345     * particular, block_pool_alloc() increments state->next prior to
346     * calling block_pool_grow, so this ensures that we get enough space for
347     * which ever side tries to grow the pool.
348     *
349     * We align to a page size because it makes it easier to do our
350     * calculations later in such a way that we state page-aigned.
351     */
352    uint32_t back_used = align_u32(pool->back_state.next, PAGE_SIZE);
353    uint32_t front_used = align_u32(pool->state.next, PAGE_SIZE);
354    uint32_t total_used = front_used + back_used;
355
356    assert(state == &pool->state || back_used > 0);
357
358    size_t old_size = pool->bo.size;
359
360    if (old_size != 0 &&
361        back_used * 2 <= pool->center_bo_offset &&
362        front_used * 2 <= (old_size - pool->center_bo_offset)) {
363       /* If we're in this case then this isn't the firsta allocation and we
364        * already have enough space on both sides to hold double what we
365        * have allocated.  There's nothing for us to do.
366        */
367       goto done;
368    }
369
370    if (old_size == 0) {
371       /* This is the first allocation */
372       size = MAX2(32 * pool->block_size, PAGE_SIZE);
373    } else {
374       size = old_size * 2;
375    }
376
377    /* We can't have a block pool bigger than 1GB because we use signed
378     * 32-bit offsets in the free list and we don't want overflow.  We
379     * should never need a block pool bigger than 1GB anyway.
380     */
381    assert(size <= (1u << 31));
382
383    /* We compute a new center_bo_offset such that, when we double the size
384     * of the pool, we maintain the ratio of how much is used by each side.
385     * This way things should remain more-or-less balanced.
386     */
387    uint32_t center_bo_offset;
388    if (back_used == 0) {
389       /* If we're in this case then we have never called alloc_back().  In
390        * this case, we want keep the offset at 0 to make things as simple
391        * as possible for users that don't care about back allocations.
392        */
393       center_bo_offset = 0;
394    } else {
395       /* Try to "center" the allocation based on how much is currently in
396        * use on each side of the center line.
397        */
398       center_bo_offset = ((uint64_t)size * back_used) / total_used;
399
400       /* Align down to a multiple of both the block size and page size */
401       uint32_t granularity = MAX2(pool->block_size, PAGE_SIZE);
402       assert(util_is_power_of_two(granularity));
403       center_bo_offset &= ~(granularity - 1);
404
405       assert(center_bo_offset >= back_used);
406
407       /* Make sure we don't shrink the back end of the pool */
408       if (center_bo_offset < pool->back_state.end)
409          center_bo_offset = pool->back_state.end;
410
411       /* Make sure that we don't shrink the front end of the pool */
412       if (size - center_bo_offset < pool->state.end)
413          center_bo_offset = size - pool->state.end;
414    }
415
416    assert(center_bo_offset % pool->block_size == 0);
417    assert(center_bo_offset % PAGE_SIZE == 0);
418
419    /* Assert that we only ever grow the pool */
420    assert(center_bo_offset >= pool->back_state.end);
421    assert(size - center_bo_offset >= pool->state.end);
422
423    cleanup = anv_vector_add(&pool->mmap_cleanups);
424    if (!cleanup)
425       goto fail;
426    *cleanup = ANV_MMAP_CLEANUP_INIT;
427
428    /* Just leak the old map until we destroy the pool.  We can't munmap it
429     * without races or imposing locking on the block allocate fast path. On
430     * the whole the leaked maps adds up to less than the size of the
431     * current map.  MAP_POPULATE seems like the right thing to do, but we
432     * should try to get some numbers.
433     */
434    map = mmap(NULL, size, PROT_READ | PROT_WRITE,
435               MAP_SHARED | MAP_POPULATE, pool->fd,
436               BLOCK_POOL_MEMFD_CENTER - center_bo_offset);
437    cleanup->map = map;
438    cleanup->size = size;
439
440    if (map == MAP_FAILED)
441       goto fail;
442
443    gem_handle = anv_gem_userptr(pool->device, map, size);
444    if (gem_handle == 0)
445       goto fail;
446    cleanup->gem_handle = gem_handle;
447
448 #if 0
449    /* Regular objects are created I915_CACHING_CACHED on LLC platforms and
450     * I915_CACHING_NONE on non-LLC platforms. However, userptr objects are
451     * always created as I915_CACHING_CACHED, which on non-LLC means
452     * snooped. That can be useful but comes with a bit of overheard.  Since
453     * we're eplicitly clflushing and don't want the overhead we need to turn
454     * it off. */
455    if (!pool->device->info.has_llc) {
456       anv_gem_set_caching(pool->device, gem_handle, I915_CACHING_NONE);
457       anv_gem_set_domain(pool->device, gem_handle,
458                          I915_GEM_DOMAIN_GTT, I915_GEM_DOMAIN_GTT);
459    }
460 #endif
461
462    /* Now that we successfull allocated everything, we can write the new
463     * values back into pool. */
464    pool->map = map + center_bo_offset;
465    pool->center_bo_offset = center_bo_offset;
466    pool->bo.gem_handle = gem_handle;
467    pool->bo.size = size;
468    pool->bo.map = map;
469    pool->bo.index = 0;
470
471 done:
472    pthread_mutex_unlock(&pool->device->mutex);
473
474    /* Return the appropreate new size.  This function never actually
475     * updates state->next.  Instead, we let the caller do that because it
476     * needs to do so in order to maintain its concurrency model.
477     */
478    if (state == &pool->state) {
479       return pool->bo.size - pool->center_bo_offset;
480    } else {
481       assert(pool->center_bo_offset > 0);
482       return pool->center_bo_offset;
483    }
484
485 fail:
486    pthread_mutex_unlock(&pool->device->mutex);
487
488    return 0;
489 }
490
491 static uint32_t
492 anv_block_pool_alloc_new(struct anv_block_pool *pool,
493                          struct anv_block_state *pool_state)
494 {
495    struct anv_block_state state, old, new;
496
497    while (1) {
498       state.u64 = __sync_fetch_and_add(&pool_state->u64, pool->block_size);
499       if (state.next < state.end) {
500          assert(pool->map);
501          return state.next;
502       } else if (state.next == state.end) {
503          /* We allocated the first block outside the pool, we have to grow it.
504           * pool_state->next acts a mutex: threads who try to allocate now will
505           * get block indexes above the current limit and hit futex_wait
506           * below. */
507          new.next = state.next + pool->block_size;
508          new.end = anv_block_pool_grow(pool, pool_state);
509          assert(new.end >= new.next && new.end % pool->block_size == 0);
510          old.u64 = __sync_lock_test_and_set(&pool_state->u64, new.u64);
511          if (old.next != state.next)
512             futex_wake(&pool_state->end, INT_MAX);
513          return state.next;
514       } else {
515          futex_wait(&pool_state->end, state.end);
516          continue;
517       }
518    }
519 }
520
521 int32_t
522 anv_block_pool_alloc(struct anv_block_pool *pool)
523 {
524    int32_t offset;
525
526    /* Try free list first. */
527    if (anv_free_list_pop(&pool->free_list, &pool->map, &offset)) {
528       assert(offset >= 0);
529       assert(pool->map);
530       return offset;
531    }
532
533    return anv_block_pool_alloc_new(pool, &pool->state);
534 }
535
536 /* Allocates a block out of the back of the block pool.
537  *
538  * This will allocated a block earlier than the "start" of the block pool.
539  * The offsets returned from this function will be negative but will still
540  * be correct relative to the block pool's map pointer.
541  *
542  * If you ever use anv_block_pool_alloc_back, then you will have to do
543  * gymnastics with the block pool's BO when doing relocations.
544  */
545 int32_t
546 anv_block_pool_alloc_back(struct anv_block_pool *pool)
547 {
548    int32_t offset;
549
550    /* Try free list first. */
551    if (anv_free_list_pop(&pool->back_free_list, &pool->map, &offset)) {
552       assert(offset < 0);
553       assert(pool->map);
554       return offset;
555    }
556
557    offset = anv_block_pool_alloc_new(pool, &pool->back_state);
558
559    /* The offset we get out of anv_block_pool_alloc_new() is actually the
560     * number of bytes downwards from the middle to the end of the block.
561     * We need to turn it into a (negative) offset from the middle to the
562     * start of the block.
563     */
564    assert(offset >= 0);
565    return -(offset + pool->block_size);
566 }
567
568 void
569 anv_block_pool_free(struct anv_block_pool *pool, int32_t offset)
570 {
571    if (offset < 0) {
572       anv_free_list_push(&pool->back_free_list, pool->map, offset);
573    } else {
574       anv_free_list_push(&pool->free_list, pool->map, offset);
575    }
576 }
577
578 static void
579 anv_fixed_size_state_pool_init(struct anv_fixed_size_state_pool *pool,
580                                size_t state_size)
581 {
582    /* At least a cache line and must divide the block size. */
583    assert(state_size >= 64 && util_is_power_of_two(state_size));
584
585    pool->state_size = state_size;
586    pool->free_list = ANV_FREE_LIST_EMPTY;
587    pool->block.next = 0;
588    pool->block.end = 0;
589 }
590
591 static uint32_t
592 anv_fixed_size_state_pool_alloc(struct anv_fixed_size_state_pool *pool,
593                                 struct anv_block_pool *block_pool)
594 {
595    int32_t offset;
596    struct anv_block_state block, old, new;
597
598    /* Try free list first. */
599    if (anv_free_list_pop(&pool->free_list, &block_pool->map, &offset)) {
600       assert(offset >= 0);
601       return offset;
602    }
603
604    /* If free list was empty (or somebody raced us and took the items) we
605     * allocate a new item from the end of the block */
606  restart:
607    block.u64 = __sync_fetch_and_add(&pool->block.u64, pool->state_size);
608
609    if (block.next < block.end) {
610       return block.next;
611    } else if (block.next == block.end) {
612       offset = anv_block_pool_alloc(block_pool);
613       new.next = offset + pool->state_size;
614       new.end = offset + block_pool->block_size;
615       old.u64 = __sync_lock_test_and_set(&pool->block.u64, new.u64);
616       if (old.next != block.next)
617          futex_wake(&pool->block.end, INT_MAX);
618       return offset;
619    } else {
620       futex_wait(&pool->block.end, block.end);
621       goto restart;
622    }
623 }
624
625 static void
626 anv_fixed_size_state_pool_free(struct anv_fixed_size_state_pool *pool,
627                                struct anv_block_pool *block_pool,
628                                uint32_t offset)
629 {
630    anv_free_list_push(&pool->free_list, block_pool->map, offset);
631 }
632
633 void
634 anv_state_pool_init(struct anv_state_pool *pool,
635                     struct anv_block_pool *block_pool)
636 {
637    pool->block_pool = block_pool;
638    for (unsigned i = 0; i < ANV_STATE_BUCKETS; i++) {
639       size_t size = 1 << (ANV_MIN_STATE_SIZE_LOG2 + i);
640       anv_fixed_size_state_pool_init(&pool->buckets[i], size);
641    }
642    VG(VALGRIND_CREATE_MEMPOOL(pool, 0, false));
643 }
644
645 void
646 anv_state_pool_finish(struct anv_state_pool *pool)
647 {
648    VG(VALGRIND_DESTROY_MEMPOOL(pool));
649 }
650
651 struct anv_state
652 anv_state_pool_alloc(struct anv_state_pool *pool, size_t size, size_t align)
653 {
654    unsigned size_log2 = ilog2_round_up(size < align ? align : size);
655    assert(size_log2 <= ANV_MAX_STATE_SIZE_LOG2);
656    if (size_log2 < ANV_MIN_STATE_SIZE_LOG2)
657       size_log2 = ANV_MIN_STATE_SIZE_LOG2;
658    unsigned bucket = size_log2 - ANV_MIN_STATE_SIZE_LOG2;
659
660    struct anv_state state;
661    state.alloc_size = 1 << size_log2;
662    state.offset = anv_fixed_size_state_pool_alloc(&pool->buckets[bucket],
663                                                   pool->block_pool);
664    state.map = pool->block_pool->map + state.offset;
665    VG(VALGRIND_MEMPOOL_ALLOC(pool, state.map, size));
666    return state;
667 }
668
669 void
670 anv_state_pool_free(struct anv_state_pool *pool, struct anv_state state)
671 {
672    assert(util_is_power_of_two(state.alloc_size));
673    unsigned size_log2 = ilog2_round_up(state.alloc_size);
674    assert(size_log2 >= ANV_MIN_STATE_SIZE_LOG2 &&
675           size_log2 <= ANV_MAX_STATE_SIZE_LOG2);
676    unsigned bucket = size_log2 - ANV_MIN_STATE_SIZE_LOG2;
677
678    VG(VALGRIND_MEMPOOL_FREE(pool, state.map));
679    anv_fixed_size_state_pool_free(&pool->buckets[bucket],
680                                   pool->block_pool, state.offset);
681 }
682
683 #define NULL_BLOCK 1
684 struct anv_state_stream_block {
685    /* The next block */
686    struct anv_state_stream_block *next;
687
688    /* The offset into the block pool at which this block starts */
689    uint32_t offset;
690
691 #ifdef HAVE_VALGRIND
692    /* A pointer to the first user-allocated thing in this block.  This is
693     * what valgrind sees as the start of the block.
694     */
695    void *_vg_ptr;
696 #endif
697 };
698
699 /* The state stream allocator is a one-shot, single threaded allocator for
700  * variable sized blocks.  We use it for allocating dynamic state.
701  */
702 void
703 anv_state_stream_init(struct anv_state_stream *stream,
704                       struct anv_block_pool *block_pool)
705 {
706    stream->block_pool = block_pool;
707    stream->block = NULL;
708
709    /* Ensure that next + whatever > end.  This way the first call to
710     * state_stream_alloc fetches a new block.
711     */
712    stream->next = 1;
713    stream->end = 0;
714
715    VG(VALGRIND_CREATE_MEMPOOL(stream, 0, false));
716 }
717
718 void
719 anv_state_stream_finish(struct anv_state_stream *stream)
720 {
721    VG(const uint32_t block_size = stream->block_pool->block_size);
722
723    struct anv_state_stream_block *next = stream->block;
724    while (next != NULL) {
725       VG(VALGRIND_MAKE_MEM_DEFINED(next, sizeof(*next)));
726       struct anv_state_stream_block sb = VG_NOACCESS_READ(next);
727       VG(VALGRIND_MEMPOOL_FREE(stream, sb._vg_ptr));
728       VG(VALGRIND_MAKE_MEM_UNDEFINED(next, block_size));
729       anv_block_pool_free(stream->block_pool, sb.offset);
730       next = sb.next;
731    }
732
733    VG(VALGRIND_DESTROY_MEMPOOL(stream));
734 }
735
736 struct anv_state
737 anv_state_stream_alloc(struct anv_state_stream *stream,
738                        uint32_t size, uint32_t alignment)
739 {
740    struct anv_state_stream_block *sb = stream->block;
741
742    struct anv_state state;
743
744    state.offset = align_u32(stream->next, alignment);
745    if (state.offset + size > stream->end) {
746       uint32_t block = anv_block_pool_alloc(stream->block_pool);
747       sb = stream->block_pool->map + block;
748
749       VG(VALGRIND_MAKE_MEM_UNDEFINED(sb, sizeof(*sb)));
750       sb->next = stream->block;
751       sb->offset = block;
752       VG(sb->_vg_ptr = NULL);
753       VG(VALGRIND_MAKE_MEM_NOACCESS(sb, stream->block_pool->block_size));
754
755       stream->block = sb;
756       stream->start = block;
757       stream->next = block + sizeof(*sb);
758       stream->end = block + stream->block_pool->block_size;
759
760       state.offset = align_u32(stream->next, alignment);
761       assert(state.offset + size <= stream->end);
762    }
763
764    assert(state.offset > stream->start);
765    state.map = (void *)sb + (state.offset - stream->start);
766    state.alloc_size = size;
767
768 #ifdef HAVE_VALGRIND
769    void *vg_ptr = VG_NOACCESS_READ(&sb->_vg_ptr);
770    if (vg_ptr == NULL) {
771       vg_ptr = state.map;
772       VG_NOACCESS_WRITE(&sb->_vg_ptr, vg_ptr);
773       VALGRIND_MEMPOOL_ALLOC(stream, vg_ptr, size);
774    } else {
775       void *state_end = state.map + state.alloc_size;
776       /* This only updates the mempool.  The newly allocated chunk is still
777        * marked as NOACCESS. */
778       VALGRIND_MEMPOOL_CHANGE(stream, vg_ptr, vg_ptr, state_end - vg_ptr);
779       /* Mark the newly allocated chunk as undefined */
780       VALGRIND_MAKE_MEM_UNDEFINED(state.map, state.alloc_size);
781    }
782 #endif
783
784    stream->next = state.offset + size;
785
786    return state;
787 }
788
789 struct bo_pool_bo_link {
790    struct bo_pool_bo_link *next;
791    struct anv_bo bo;
792 };
793
794 void
795 anv_bo_pool_init(struct anv_bo_pool *pool, struct anv_device *device)
796 {
797    pool->device = device;
798    memset(pool->free_list, 0, sizeof(pool->free_list));
799
800    VG(VALGRIND_CREATE_MEMPOOL(pool, 0, false));
801 }
802
803 void
804 anv_bo_pool_finish(struct anv_bo_pool *pool)
805 {
806    for (unsigned i = 0; i < ARRAY_SIZE(pool->free_list); i++) {
807       struct bo_pool_bo_link *link = PFL_PTR(pool->free_list[i]);
808       while (link != NULL) {
809          struct bo_pool_bo_link link_copy = VG_NOACCESS_READ(link);
810
811          anv_gem_munmap(link_copy.bo.map, link_copy.bo.size);
812          anv_gem_close(pool->device, link_copy.bo.gem_handle);
813          link = link_copy.next;
814       }
815    }
816
817    VG(VALGRIND_DESTROY_MEMPOOL(pool));
818 }
819
820 VkResult
821 anv_bo_pool_alloc(struct anv_bo_pool *pool, struct anv_bo *bo, uint32_t size)
822 {
823    VkResult result;
824
825    const unsigned size_log2 = size < 4096 ? 12 : ilog2_round_up(size);
826    const unsigned pow2_size = 1 << size_log2;
827    const unsigned bucket = size_log2 - 12;
828    assert(bucket < ARRAY_SIZE(pool->free_list));
829
830    void *next_free_void;
831    if (anv_ptr_free_list_pop(&pool->free_list[bucket], &next_free_void)) {
832       struct bo_pool_bo_link *next_free = next_free_void;
833       *bo = VG_NOACCESS_READ(&next_free->bo);
834       assert(bo->map == next_free);
835       assert(size <= bo->size);
836
837       VG(VALGRIND_MEMPOOL_ALLOC(pool, bo->map, size));
838
839       return VK_SUCCESS;
840    }
841
842    struct anv_bo new_bo;
843
844    result = anv_bo_init_new(&new_bo, pool->device, pow2_size);
845    if (result != VK_SUCCESS)
846       return result;
847
848    assert(new_bo.size == pow2_size);
849
850    new_bo.map = anv_gem_mmap(pool->device, new_bo.gem_handle, 0, pow2_size, 0);
851    if (new_bo.map == NULL) {
852       anv_gem_close(pool->device, new_bo.gem_handle);
853       return vk_error(VK_ERROR_MEMORY_MAP_FAILED);
854    }
855
856    *bo = new_bo;
857
858    VG(VALGRIND_MEMPOOL_ALLOC(pool, bo->map, size));
859
860    return VK_SUCCESS;
861 }
862
863 void
864 anv_bo_pool_free(struct anv_bo_pool *pool, const struct anv_bo *bo_in)
865 {
866    /* Make a copy in case the anv_bo happens to be storred in the BO */
867    struct anv_bo bo = *bo_in;
868    struct bo_pool_bo_link *link = bo.map;
869    link->bo = bo;
870
871    assert(util_is_power_of_two(bo.size));
872    const unsigned size_log2 = ilog2_round_up(bo.size);
873    const unsigned bucket = size_log2 - 12;
874    assert(bucket < ARRAY_SIZE(pool->free_list));
875
876    VG(VALGRIND_MEMPOOL_FREE(pool, bo.map));
877    anv_ptr_free_list_push(&pool->free_list[bucket], link);
878 }
879
880 // Scratch pool
881
882 void
883 anv_scratch_pool_init(struct anv_device *device, struct anv_scratch_pool *pool)
884 {
885    memset(pool, 0, sizeof(*pool));
886 }
887
888 void
889 anv_scratch_pool_finish(struct anv_device *device, struct anv_scratch_pool *pool)
890 {
891    for (unsigned s = 0; s < MESA_SHADER_STAGES; s++) {
892       for (unsigned i = 0; i < 16; i++) {
893          struct anv_bo *bo = &pool->bos[i][s];
894          if (bo->size > 0)
895             anv_gem_close(device, bo->gem_handle);
896       }
897    }
898 }
899
900 struct anv_bo *
901 anv_scratch_pool_alloc(struct anv_device *device, struct anv_scratch_pool *pool,
902                        gl_shader_stage stage, unsigned per_thread_scratch)
903 {
904    if (per_thread_scratch == 0)
905       return NULL;
906
907    unsigned scratch_size_log2 = ffs(per_thread_scratch / 2048);
908    assert(scratch_size_log2 < 16);
909
910    struct anv_bo *bo = &pool->bos[scratch_size_log2][stage];
911
912    /* From now on, we go into a critical section.  In order to remain
913     * thread-safe, we use the bo size as a lock.  A value of 0 means we don't
914     * have a valid BO yet.  A value of 1 means locked.  A value greater than 1
915     * means we have a bo of the given size.
916     */
917
918    if (bo->size > 1)
919       return bo;
920
921    uint64_t size = __sync_val_compare_and_swap(&bo->size, 0, 1);
922    if (size == 0) {
923       /* We own the lock.  Allocate a buffer */
924
925       struct brw_device_info *devinfo = &device->info;
926       uint32_t max_threads[] = {
927          [MESA_SHADER_VERTEX]                  = devinfo->max_vs_threads,
928          [MESA_SHADER_TESS_CTRL]               = devinfo->max_hs_threads,
929          [MESA_SHADER_TESS_EVAL]               = devinfo->max_ds_threads,
930          [MESA_SHADER_GEOMETRY]                = devinfo->max_gs_threads,
931          [MESA_SHADER_FRAGMENT]                = devinfo->max_wm_threads,
932          [MESA_SHADER_COMPUTE]                 = devinfo->max_cs_threads,
933       };
934
935       size = per_thread_scratch * max_threads[stage];
936
937       struct anv_bo new_bo;
938       anv_bo_init_new(&new_bo, device, size);
939
940       bo->gem_handle = new_bo.gem_handle;
941
942       /* Set the size last because we use it as a lock */
943       __sync_synchronize();
944       bo->size = size;
945
946       futex_wake((uint32_t *)&bo->size, INT_MAX);
947    } else {
948       /* Someone else got here first */
949       while (bo->size == 1)
950          futex_wait((uint32_t *)&bo->size, 1);
951    }
952
953    return bo;
954 }