diff options
Diffstat (limited to 'drivers/gpu/nvgpu/common/mm/lockless_allocator_priv.h')
-rw-r--r-- | drivers/gpu/nvgpu/common/mm/lockless_allocator_priv.h | 127 |
1 files changed, 127 insertions, 0 deletions
diff --git a/drivers/gpu/nvgpu/common/mm/lockless_allocator_priv.h b/drivers/gpu/nvgpu/common/mm/lockless_allocator_priv.h new file mode 100644 index 00000000..c2f6649a --- /dev/null +++ b/drivers/gpu/nvgpu/common/mm/lockless_allocator_priv.h | |||
@@ -0,0 +1,127 @@ | |||
1 | /* | ||
2 | * Copyright (c) 2016 - 2017, NVIDIA CORPORATION. All rights reserved. | ||
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 shall be included in | ||
12 | * all copies or substantial portions of the Software. | ||
13 | * | ||
14 | * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR | ||
15 | * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, | ||
16 | * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL | ||
17 | * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER | ||
18 | * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING | ||
19 | * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER | ||
20 | * DEALINGS IN THE SOFTWARE. | ||
21 | */ | ||
22 | |||
23 | /* | ||
24 | * Basics: | ||
25 | * | ||
26 | * - Lockless memory allocator for fixed-size structures, whose | ||
27 | * size is defined up front at init time. | ||
28 | * - Memory footprint scales linearly w/ the number of structures in | ||
29 | * the pool. It is ~= sizeof(int) * N. | ||
30 | * - Memory is pre-allocated by the client. The allocator itself | ||
31 | * only computes the addresses for allocations. | ||
32 | * - Limit of MAX_INT nodes that the allocator can be responsible for. | ||
33 | * | ||
34 | * Implementation details: | ||
35 | * | ||
36 | * The allocator maintains a single list of free nodes. We allocate & | ||
37 | * free nodes from the head of the list. We rely on the cmpxchg() operator | ||
38 | * to maintain atomicity on the head. | ||
39 | * | ||
40 | * So, both allocs & frees are O(1)!! | ||
41 | * | ||
42 | * -- Definitions -- | ||
43 | * Block Size - size of a single structure that this allocator will | ||
44 | * allocate. | ||
45 | * Node - one of the elements of size blk_size in the | ||
46 | * client-allocated buffer. | ||
47 | * Node Index - zero-based index of a node in the client-allocated | ||
48 | * contiguous buffer. | ||
49 | * | ||
50 | * -- Initial State -- | ||
51 | * We maintain the following to track the state of the free list: | ||
52 | * | ||
53 | * 1) A "head" index to track the index of the first free node in the list | ||
54 | * 2) A "next" array to track the index of the next free node in the list | ||
55 | * for every node. So next[head], will give the index to the 2nd free | ||
56 | * element in the list. | ||
57 | * | ||
58 | * So, to begin with, the free list consists of all node indices, and each | ||
59 | * position in the next array contains index N + 1: | ||
60 | * | ||
61 | * head = 0 | ||
62 | * next = [1, 2, 3, 4, -1] : Example for a user-allocated buffer of 5 nodes | ||
63 | * free_list = 0->1->2->3->4->-1 | ||
64 | * | ||
65 | * -- Allocations -- | ||
66 | * 1) Read the current head (aka acq_head) | ||
67 | * 2) Read next[acq_head], to get the 2nd free element (aka new_head) | ||
68 | * 3) cmp_xchg(&head, acq_head, new_head) | ||
69 | * 4) If it succeeds, compute the address of the node, based on | ||
70 | * base address, blk_size, & acq_head. | ||
71 | * | ||
72 | * head = 1; | ||
73 | * next = [1, 2, 3, 4, -1] : Example after allocating Node #0 | ||
74 | * free_list = 1->2->3->4->-1 | ||
75 | * | ||
76 | * head = 2; | ||
77 | * next = [1, 2, 3, 4, -1] : Example after allocating Node #1 | ||
78 | * free_list = 2->3->4->-1 | ||
79 | * | ||
80 | * -- Frees -- | ||
81 | * 1) Based on the address to be freed, calculate the index of the node | ||
82 | * being freed (cur_idx) | ||
83 | * 2) Read the current head (old_head) | ||
84 | * 3) So the freed node is going to go at the head of the list, and we | ||
85 | * want to put the old_head after it. So next[cur_idx] = old_head | ||
86 | * 4) cmpxchg(head, old_head, cur_idx) | ||
87 | * | ||
88 | * head = 0 | ||
89 | * next = [2, 2, 3, 4, -1] | ||
90 | * free_list = 0->2->3->4->-1 : Example after freeing Node #0 | ||
91 | * | ||
92 | * head = 1 | ||
93 | * next = [2, 0, 3, 4, -1] | ||
94 | * free_list = 1->0->2->3->4->-1 : Example after freeing Node #1 | ||
95 | */ | ||
96 | |||
97 | #ifndef LOCKLESS_ALLOCATOR_PRIV_H | ||
98 | #define LOCKLESS_ALLOCATOR_PRIV_H | ||
99 | |||
100 | struct nvgpu_allocator; | ||
101 | |||
102 | struct nvgpu_lockless_allocator { | ||
103 | struct nvgpu_allocator *owner; | ||
104 | |||
105 | u64 base; /* Base address of the space. */ | ||
106 | u64 length; /* Length of the space. */ | ||
107 | u64 blk_size; /* Size of the structure being allocated */ | ||
108 | int nr_nodes; /* Number of nodes available for allocation */ | ||
109 | |||
110 | int *next; /* An array holding the next indices per node */ | ||
111 | int head; /* Current node at the top of the stack */ | ||
112 | |||
113 | u64 flags; | ||
114 | |||
115 | bool inited; | ||
116 | |||
117 | /* Statistics */ | ||
118 | nvgpu_atomic_t nr_allocs; | ||
119 | }; | ||
120 | |||
121 | static inline struct nvgpu_lockless_allocator *lockless_allocator( | ||
122 | struct nvgpu_allocator *a) | ||
123 | { | ||
124 | return (struct nvgpu_lockless_allocator *)(a)->priv; | ||
125 | } | ||
126 | |||
127 | #endif | ||