1 /*
2  * simple_idr.c
3  *
4  * Copyright (c) 2007-2019 Allwinnertech Co., Ltd.
5  *
6  *
7  * This software is licensed under the terms of the GNU General Public
8  * License version 2, as published by the Free Software Foundation, and
9  * may be copied, distributed, and modified under those terms.
10  *
11  * This program is distributed in the hope that it will be useful,
12  * but WITHOUT ANY WARRANTY; without even the implied warranty of
13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
14  * GNU General Public License for more details.
15  *
16  */
17 
18 
19 //not apply it in the IRQ, a simple idr from linux
20 #include <stdio.h>
21 #include <stdio.h>
22 #include <string.h>
23 #include <stdlib.h>
24 #include "g2d_bsp.h"
25 #include "simple_idr.h"
26 
find_empty_slot(struct id_layer * up_layer,int * id_index)27 static struct id_layer** find_empty_slot(struct id_layer *up_layer, int *id_index)
28 {
29     //first  right  empty  0~31
30     int i = 0, start = 0, id = 0;
31 
32     for (i = 0; i < IDR_SIZE/32; i++)
33         if(up_layer->bitmap[i] != IDR32_MASK)
34             break;
35     if (i == IDR_SIZE/32) {
36         *id_index = NO_ID;
37         return NULL;
38     }
39 
40     if (up_layer->bitmap[i] == 0)
41         goto cal;
42     id = ~up_layer->bitmap[i];
43     // 0~31 bit
44     if (!(id&0x0000ffff)) {
45         start +=16;
46         id >>= 16;
47     }
48     if (!(id&0x00ff)) {
49         start += 8;
50         id >>= 8;
51     }
52     if (!(id&0x0f)) {
53         start += 4;
54         id >>= 4;
55     }
56     if (!(id&0x3)) {
57         start += 2;
58         id >>= 2;
59     }
60     if (!(id&0x1)) {
61         start += 1;
62         id >>= 1;
63     }
64 cal:
65     *id_index = i*32+start;
66 
67     return &up_layer->layer[*id_index];
68 }
69 
id_alloc(struct id_dir * dir,void * value)70 int id_alloc(struct id_dir *dir, void *value)
71 {
72     int id = NO_ID, id_index = NO_ID;
73     int i = 0;
74     int curr_lvl;
75     struct id_layer **cur = NULL, *tmp = NULL;
76 
77     if (dir == NULL || dir->status == -1)
78         return NO_ID;
79 
80     hal_sem_wait(dir->lock);
81 
82     if (dir->status == -1)
83         goto out;
84     dir->status = 1;
85     if (dir->lu_cache[0] != NULL) {
86         tmp = dir->lu_cache[0];
87         id = dir->lu_id;
88         cur = find_empty_slot(tmp, &id_index);
89         id = (id&(~0xff)) + id_index;
90     }else{
91         //add a new top
92         if (dir->top == NULL || find_empty_slot(dir->top, &id_index) == NULL) {
93             if (dir->top && dir->cur_max_level > 2) {
94                 G2D_INFO_MSG("a full idr,we only support 32bit\n");
95                 goto out;
96             }
97             tmp = (struct id_layer*)hal_malloc(sizeof(struct id_layer));
98 	    memset(tmp, 0, sizeof(struct id_layer));
99             tmp->layer[0] = dir->top;
100             tmp->bitmap[0] = 0x01;//0 is NO_ID
101             tmp->num_layer = 1;
102             dir->cur_max_level++;
103             dir->top = tmp;
104             if (dir->head) {
105                 dir->head->pre = tmp;
106             }
107             tmp->next = dir->head;
108         }
109         curr_lvl = dir->cur_max_level;
110         for (cur= &dir->top; *cur != NULL; id <<= 8, id += id_index, curr_lvl--) {
111             tmp = *cur;
112             dir->lu_cache[curr_lvl] = tmp;
113             cur = find_empty_slot(tmp, &id_index);
114             if (curr_lvl > 0 && *cur == NULL) {
115                 //add a new child idr
116                 *cur = (struct id_layer*)hal_malloc(sizeof(struct id_layer));
117                 if (*cur == NULL) {
118                     G2D_INFO_MSG("atomic alloc idr mem err.\n");
119                     goto out;
120                 }
121 		memset(*cur, 0, sizeof(struct id_layer));
122                 tmp->num_layer++;
123                 (*cur)->next = dir->head;
124                 (*cur)->pre = NULL;
125                 dir->head = *cur;
126             }
127         }
128     }
129 
130     dir->lu_id = id;
131     *cur = (struct id_layer*)value;
132     tmp->bitmap[id_index/32] |= 1 << (id_index%32);
133     tmp->num_layer++;
134 
135     if (tmp->num_layer == IDR_SIZE) {
136         dir->lu_cache[0] = NULL;
137         for (i = 1; dir->lu_cache[i] != NULL && i < dir->cur_max_level; i++) {
138             id_index = (id>>(8*i)) & 0xff;
139             dir->lu_cache[i]->bitmap[id_index/32] |= 1 << (id_index%32);
140             if (find_empty_slot(dir->lu_cache[i], &id_index) != NULL) {
141                 break;
142             }
143         }
144     }
145     dir->status = 0;
146 out:
147     hal_sem_post(dir->lock);
148    // printf("id_alloc:%d == %08x\n",id, value);
149 
150     return id;
151 }
152 
id_free(struct id_dir * dir,int id)153 void id_free(struct id_dir *dir, int id)
154 {
155     struct id_layer* lu[4] = {NULL, NULL, NULL, NULL};
156 
157     int i = 0, id_index = 0;
158     if (id>>((dir->cur_max_level+1)*8) || id == NO_ID
159             || dir->top == NULL || dir->status == -1) {
160         G2D_INFO_MSG("give a err id:%d, max:%ld\n", id, (1ul << ((dir->cur_max_level+1)* 8)) - 1);
161         return;
162     }
163 
164     hal_sem_wait(dir->lock);
165 
166     if (dir->status == -1)
167         goto out;
168     dir->status = 1;
169     lu[dir->cur_max_level] = dir->top;
170     for (i = dir->cur_max_level; i > 0; ) {
171         id_index = (id>>(i*8)) & 0xff;
172         i--;
173         lu[i] = lu[i+1]->layer[id_index];
174     }
175     id_index = id&0xff;
176     lu[0]->layer[id_index] = NULL;
177     lu[0]->num_layer--;
178     lu[0]->bitmap[id_index/32] &= ~(1<<(id_index % 32));
179 
180     for (i = 1; i <= dir->cur_max_level; i++) {
181         id_index =  (id>>(i*8)) & 0xff;
182         lu[i]->bitmap[id_index/32] &= ~(1<<(id_index % 32));
183 
184         if (lu[i-1]->num_layer == 0) {
185             //top will not empty due to NO_ID, least 1 top layer.
186             if (lu[i]->layer[id_index]->next != NULL)
187                 lu[i]->layer[id_index]->next->pre = lu[i]->layer[id_index]->pre;
188             if (lu[i]->layer[id_index]->pre != NULL)
189                 lu[i]->layer[id_index]->pre->next = lu[i]->layer[id_index]->next;
190             else
191                 dir->head = lu[i]->layer[id_index]->next;
192             free(lu[i]->layer[id_index]);
193             lu[i]->layer[id_index] = NULL;
194             lu[i]->num_layer--;
195         }
196     }
197 
198 //deal_top:
199     while (dir->top->num_layer == 1 && dir->cur_max_level > 0
200             && dir->top->layer[0] != NULL && dir->top->bitmap[0]^0x01) {
201         lu[0] = dir->top;
202         dir->top = lu[0]->layer[0];
203         if (lu[0]->next != NULL)
204             lu[0]->next->pre = lu[0]->pre;
205         if (lu[0]->pre != NULL)
206             lu[0]->pre->next = lu[0]->next;
207         else
208             dir->head = lu[0]->next;
209         free(lu[0]);
210 
211         dir->cur_max_level--;
212     }
213     dir->status = 0;
214 out:
215     hal_sem_post(dir->lock);
216     //printf("leave id_free: %d \n", id);
217 }
218 
id_get(struct id_dir * dir,int id)219 void* id_get(struct id_dir *dir, int id)
220 {
221     int id_index, i;
222     struct id_layer *lu = NULL;
223 
224     if (dir == NULL || dir->top == NULL || dir->status == -1 || id == NO_ID)
225         return NULL;
226     //the atomic area , but not happen
227     if (id>>((dir->cur_max_level+1)*8))
228         return NULL;
229 
230     hal_sem_wait(dir->lock);
231     if (dir->status == -1)
232         goto out;
233     dir->status = 1;
234     lu = dir->top;
235     for (i = dir->cur_max_level; i >= 0; i--) {
236         id_index = (id>>(i*8)) & 0xff;
237         lu = lu->layer[id_index];
238         if (lu == NULL) {
239             G2D_INFO_MSG("give a err id:%d\n", id);
240             goto out;
241         }
242     }
243     dir->status = 0;
244     out:
245     hal_sem_post(dir->lock);
246 	//printf("got id:%d=%08x\n",id,lu);
247     return (void*)lu;
248 }
249 
id_creat(void)250 struct id_dir* id_creat(void)
251 {
252     struct id_dir* idr;
253     int i;
254     idr = (struct id_dir*)hal_malloc(sizeof(struct id_dir));
255     if(idr == NULL) {
256         G2D_INFO_MSG("malloc idr err.\n");
257         return NULL;
258     }
259     memset(idr, 0, sizeof(struct id_dir));
260     idr->cur_max_level = -1;
261     idr->lock = hal_sem_create(1);
262     for(i = 0; i < 4; i++)
263         idr->lu_cache[i] = NULL;
264     idr->lu_id = 0;
265     idr->head = NULL;
266     idr->top = (struct id_layer*)hal_malloc(sizeof(struct id_layer));
267     if (idr->top == NULL) {
268         G2D_INFO_MSG("malloc id_layer err.\n");
269         goto out;
270     }
271     memset(idr->top, 0, sizeof(struct id_layer));
272     idr->top->bitmap[0] = 0x01; //0 is NO_ID
273     idr->top->num_layer = 1;
274     idr->cur_max_level = 0;
275     idr->head = idr->top;
276     idr->lu_cache[0] = idr->top;
277 out:
278     return idr;
279 }
280 
id_destroyed(struct id_dir * dir)281 void id_destroyed(struct id_dir *dir)
282 {
283     struct id_layer* free_id_layer;
284 
285     hal_sem_wait(dir->lock);
286     dir->status = -1;
287     hal_sem_post(dir->lock);
288 
289     while(dir->head != NULL) {
290         free_id_layer = dir->head;
291         dir->head = free_id_layer->next;
292         free(free_id_layer);
293     }
294     free(dir);
295 }
296