1 /*
2 * Copyright (C) 2021 Huawei Device Co., Ltd.
3 * Licensed under the Apache License, Version 2.0 (the "License");
4 * you may not use this file except in compliance with the License.
5 * You may obtain a copy of the License at
6 *
7 * http://www.apache.org/licenses/LICENSE-2.0
8 *
9 * Unless required by applicable law or agreed to in writing, software
10 * distributed under the License is distributed on an "AS IS" BASIS,
11 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 * See the License for the specific language governing permissions and
13 * limitations under the License.
14 */
15
16 #include "nstackx_database.h"
17 #include <stdint.h>
18 #include <malloc.h>
19 #include <string.h>
20 #include <securec.h>
21
22 #include "nstackx_dfinder_log.h"
23 #include "nstackx_error.h"
24 #include "nstackx_statistics.h"
25
26 #define TAG "nStackXDFinder"
27
28 #define NSTACKX_USEDMAP_ROW_SIZE 32U /* Row size suit for uint32_t */
29
30 typedef struct {
31 uint8_t *blk;
32 uint32_t *usedMap;
33 uint32_t mapSize;
34 uint32_t useCount;
35 uint32_t maxCount;
36 size_t recSize;
37 RecCompareCallback cb;
38 } DatabaseInfo;
39
GetRecordIndex(const DatabaseInfo * db,const void * rec)40 static inline int64_t GetRecordIndex(const DatabaseInfo *db, const void *rec)
41 {
42 if (db->recSize == 0) {
43 return -1;
44 }
45 return ((uint8_t *)rec - db->blk) / db->recSize;
46 }
47
48 /* Make sure that recNum is valid */
IsRecordOccupied(const DatabaseInfo * db,uint32_t recNum,uint32_t * iptr,uint32_t * offptr)49 static uint8_t IsRecordOccupied(const DatabaseInfo *db, uint32_t recNum, uint32_t *iptr, uint32_t *offptr)
50 {
51 uint32_t i;
52 uint32_t off;
53
54 i = recNum / NSTACKX_USEDMAP_ROW_SIZE;
55 off = recNum % NSTACKX_USEDMAP_ROW_SIZE;
56 if (iptr != NULL) {
57 *iptr = i;
58 }
59 if (offptr != NULL) {
60 *offptr = off;
61 }
62 if (db->usedMap[i] & (1U << off)) {
63 return NSTACKX_TRUE;
64 }
65 return NSTACKX_FALSE;
66 }
67
GetRecord(const DatabaseInfo * db,uint32_t index)68 static inline void *GetRecord(const DatabaseInfo *db, uint32_t index)
69 {
70 return db->blk + (index * db->recSize);
71 }
72
DatabaseSearchRecord(const void * dbptr,void * ptr)73 void *DatabaseSearchRecord(const void *dbptr, void *ptr)
74 {
75 const DatabaseInfo *db = dbptr;
76 void *rec = NULL;
77 uint32_t i, j;
78
79 if (dbptr == NULL || ptr == NULL || db->cb == NULL) {
80 return NULL;
81 }
82
83 for (i = 0; i < db->mapSize; i++) {
84 if (!db->usedMap[i]) {
85 continue;
86 }
87 for (j = 0; j < NSTACKX_USEDMAP_ROW_SIZE; j++) {
88 if (!(db->usedMap[i] & (1U << j))) {
89 continue;
90 }
91 rec = GetRecord(db, i * NSTACKX_USEDMAP_ROW_SIZE + j);
92 if (db->cb(rec, ptr)) {
93 return rec;
94 }
95 }
96 }
97 return NULL;
98 }
99
GetDatabaseUseCount(const void * dbptr)100 uint32_t GetDatabaseUseCount(const void *dbptr)
101 {
102 if (dbptr == NULL) {
103 return 0;
104 }
105
106 return ((const DatabaseInfo *)dbptr)->useCount;
107 }
108
DatabaseGetNextRecord(void * dbptr,int64_t * idx)109 void *DatabaseGetNextRecord(void *dbptr, int64_t *idx)
110 {
111 DatabaseInfo *db = dbptr;
112 void *rec = NULL;
113 uint32_t i;
114
115 if (dbptr == NULL || idx == NULL || *idx >= UINT32_MAX) {
116 return NULL;
117 }
118 if (*idx >= 0) {
119 *idx = *idx + 1;
120 } else {
121 *idx = 0;
122 }
123
124 for (i = (uint32_t)(*idx); i < db->maxCount; i++) {
125 if (IsRecordOccupied(db, i, NULL, NULL)) {
126 rec = GetRecord(db, i);
127 *idx = (int64_t)i;
128 return rec;
129 }
130 }
131 return NULL;
132 }
133
DatabaseAllocRecordEx(void * dbptr)134 static void *DatabaseAllocRecordEx(void *dbptr)
135 {
136 DatabaseInfo *db = dbptr;
137 void *rec = NULL;
138 uint32_t i, j;
139
140 if (dbptr == NULL) {
141 return NULL;
142 }
143
144 if (db->useCount >= db->maxCount) {
145 DFINDER_LOGE(TAG, "DB max limit exceeded maxcnt:%u, usecnt:%u", db->maxCount, db->useCount);
146 return NULL;
147 }
148
149 for (i = 0; i < db->mapSize; i++) {
150 if (db->usedMap[i] == ~(uint32_t)0) {
151 continue;
152 }
153 for (j = 0; j < NSTACKX_USEDMAP_ROW_SIZE; j++) {
154 if (db->usedMap[i] & (1U << j)) {
155 continue;
156 }
157 rec = GetRecord(db, i * NSTACKX_USEDMAP_ROW_SIZE + j);
158 if (memset_s(rec, db->recSize, 0, db->recSize) != EOK) {
159 return NULL;
160 } else {
161 db->usedMap[i] |= (1U << j);
162 db->useCount++;
163 return rec;
164 }
165 }
166 }
167 return NULL;
168 }
169
DatabaseAllocRecord(void * dbptr)170 void *DatabaseAllocRecord(void *dbptr)
171 {
172 void *record = DatabaseAllocRecordEx(dbptr);
173 if (record == NULL) {
174 IncStatistics(STATS_ALLOC_RECORD_FAILED);
175 }
176 return record;
177 }
178
DatabaseFreeRecordEx(void * dbptr,const void * ptr)179 static int32_t DatabaseFreeRecordEx(void *dbptr, const void *ptr)
180 {
181 DatabaseInfo *db = dbptr;
182 uint32_t i, off;
183 int64_t recNum;
184
185 if (dbptr == NULL || ptr == NULL || db->useCount == 0) {
186 DFINDER_LOGE(TAG, "Sanity chk failed");
187 return -1;
188 }
189
190 recNum = GetRecordIndex(db, ptr);
191 if (recNum < 0 || recNum >= db->maxCount) {
192 DFINDER_LOGE(TAG, "Invalid record");
193 return -1;
194 }
195 if (!IsRecordOccupied(db, (uint32_t)recNum, &i, &off)) {
196 DFINDER_LOGE(TAG, "Unused record");
197 return -1;
198 }
199
200 db->usedMap[i] &= ~(1U << off);
201 db->useCount--;
202 return 0;
203 }
204
DatabaseFreeRecord(void * dbptr,const void * ptr)205 void DatabaseFreeRecord(void *dbptr, const void *ptr)
206 {
207 if (DatabaseFreeRecordEx(dbptr, ptr) != 0) {
208 IncStatistics(STATS_FREE_RECORD_FAILED);
209 }
210 }
211
DatabaseClean(void * ptr)212 void DatabaseClean(void *ptr)
213 {
214 DatabaseInfo *db = ptr;
215 if (db == NULL) {
216 return;
217 }
218 free(db->blk);
219 free(db->usedMap);
220 free(db);
221 }
222
DatabaseInit(uint32_t recNumber,size_t recSize,RecCompareCallback cb)223 void *DatabaseInit(uint32_t recNumber, size_t recSize, RecCompareCallback cb)
224 {
225 DatabaseInfo *db = NULL;
226
227 if (recNumber == 0 || recSize == 0) {
228 return NULL;
229 }
230
231 db = (DatabaseInfo *)calloc(1U, sizeof(DatabaseInfo));
232 if (db == NULL) {
233 DFINDER_LOGE(TAG, "calloc dbinfo failed");
234 return NULL;
235 }
236
237 db->mapSize = recNumber / NSTACKX_USEDMAP_ROW_SIZE + 1;
238 db->usedMap = calloc(db->mapSize, sizeof(uint32_t));
239 if (db->usedMap == NULL) {
240 DFINDER_LOGE(TAG, "calloc usedmap failed");
241 free(db);
242 return NULL;
243 }
244
245 db->blk = (uint8_t *)malloc(recNumber * recSize);
246 if (db->blk == NULL) {
247 DFINDER_LOGE(TAG, "malloc %u %zu failed", recNumber, recSize);
248 free(db->usedMap);
249 free(db);
250 return NULL;
251 }
252
253 db->maxCount = recNumber;
254 db->useCount = 0;
255 db->recSize = recSize;
256 db->cb = cb;
257
258 return db;
259 }
260