1 /*
2 * Copyright (c) 2011-2012, 2014-2018 The Linux Foundation. All rights reserved.
3 * Copyright (c) 2022 Qualcomm Innovation Center, Inc. All rights reserved.
4 *
5 * Permission to use, copy, modify, and/or distribute this software for
6 * any purpose with or without fee is hereby granted, provided that the
7 * above copyright notice and this permission notice appear in all
8 * copies.
9 *
10 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL
11 * WARRANTIES WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED
12 * WARRANTIES OF MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE
13 * AUTHOR BE LIABLE FOR ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL
14 * DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR
15 * PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER
16 * TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
17 * PERFORMANCE OF THIS SOFTWARE.
18 */
19
20 /*
21 * DOC: csr_link_list.c
22 *
23 * Implementation for the Common link list interfaces.
24 */
25 #include "csr_link_list.h"
26 #include "qdf_lock.h"
27 #include "qdf_mem.h"
28 #include "qdf_trace.h"
29 #include "qdf_mc_timer.h"
30 #include "sme_api.h"
31
csr_list_init(tListElem * pList)32 static inline void csr_list_init(tListElem *pList)
33 {
34 pList->last = pList->next = pList;
35 }
36
csr_list_remove_entry(tListElem * pEntry)37 static inline void csr_list_remove_entry(tListElem *pEntry)
38 {
39 tListElem *pLast;
40 tListElem *pNext;
41
42 pLast = pEntry->last;
43 pNext = pEntry->next;
44 pLast->next = pNext;
45 pNext->last = pLast;
46 }
47
csr_list_remove_head(tListElem * pHead)48 static inline tListElem *csr_list_remove_head(tListElem *pHead)
49 {
50 tListElem *pEntry;
51 tListElem *pNext;
52
53 pEntry = pHead->next;
54 pNext = pEntry->next;
55 pHead->next = pNext;
56 pNext->last = pHead;
57
58 return pEntry;
59 }
60
csr_list_remove_tail(tListElem * pHead)61 static inline tListElem *csr_list_remove_tail(tListElem *pHead)
62 {
63 tListElem *pEntry;
64 tListElem *pLast;
65
66 pEntry = pHead->last;
67 pLast = pEntry->last;
68 pHead->last = pLast;
69 pLast->next = pHead;
70
71 return pEntry;
72 }
73
csr_list_insert_tail(tListElem * pHead,tListElem * pEntry)74 static inline void csr_list_insert_tail(tListElem *pHead, tListElem *pEntry)
75 {
76 tListElem *pLast;
77
78 pLast = pHead->last;
79 pEntry->last = pLast;
80 pEntry->next = pHead;
81 pLast->next = pEntry;
82 pHead->last = pEntry;
83 }
84
csr_list_insert_head(tListElem * pHead,tListElem * pEntry)85 static inline void csr_list_insert_head(tListElem *pHead, tListElem *pEntry)
86 {
87 tListElem *pNext;
88
89 pNext = pHead->next;
90 pEntry->next = pNext;
91 pEntry->last = pHead;
92 pNext->last = pEntry;
93 pHead->next = pEntry;
94 }
95
96 /* Insert pNewEntry before pEntry */
csr_list_insert_entry(tListElem * pEntry,tListElem * pNewEntry)97 static void csr_list_insert_entry(tListElem *pEntry, tListElem *pNewEntry)
98 {
99 tListElem *pLast;
100
101 if (!pEntry) {
102 sme_err("Error!! pEntry is Null");
103 return;
104 }
105
106 pLast = pEntry->last;
107 pLast->next = pNewEntry;
108 pEntry->last = pNewEntry;
109 pNewEntry->next = pEntry;
110 pNewEntry->last = pLast;
111 }
112
csr_ll_count(tDblLinkList * pList)113 uint32_t csr_ll_count(tDblLinkList *pList)
114 {
115 uint32_t c = 0;
116
117 if (!pList) {
118 sme_err("Error!! pList is Null");
119 return c;
120 }
121
122 if (pList && (LIST_FLAG_OPEN == pList->Flag))
123 c = pList->Count;
124
125 return c;
126 }
127
csr_ll_lock(tDblLinkList * pList)128 void csr_ll_lock(tDblLinkList *pList)
129 {
130
131 if (!pList) {
132 sme_err("Error!! pList is Null");
133 return;
134 }
135
136 if (LIST_FLAG_OPEN == pList->Flag)
137 qdf_mutex_acquire(&pList->Lock);
138 }
139
csr_ll_unlock(tDblLinkList * pList)140 void csr_ll_unlock(tDblLinkList *pList)
141 {
142
143 if (!pList) {
144 sme_err("Error!! pList is Null");
145 return;
146 }
147
148 if (LIST_FLAG_OPEN == pList->Flag)
149 qdf_mutex_release(&pList->Lock);
150 }
151
csr_ll_is_list_empty(tDblLinkList * pList,bool fInterlocked)152 bool csr_ll_is_list_empty(tDblLinkList *pList, bool fInterlocked)
153 {
154 bool fEmpty = true;
155
156 if (!pList) {
157 sme_err("Error!! pList is Null");
158 return fEmpty;
159 }
160
161 if (LIST_FLAG_OPEN == pList->Flag) {
162 if (fInterlocked)
163 csr_ll_lock(pList);
164
165 fEmpty = csrIsListEmpty(&pList->ListHead);
166
167 if (fInterlocked)
168 csr_ll_unlock(pList);
169 }
170 return fEmpty;
171 }
172
csr_ll_find_entry(tDblLinkList * pList,tListElem * pEntryToFind)173 bool csr_ll_find_entry(tDblLinkList *pList, tListElem *pEntryToFind)
174 {
175 bool fFound = false;
176 tListElem *pEntry;
177
178 if (!pList) {
179 sme_err("Error!! pList is Null");
180 return fFound;
181 }
182
183 if (LIST_FLAG_OPEN == pList->Flag) {
184 pEntry = csr_ll_peek_head(pList, LL_ACCESS_NOLOCK);
185
186 /* Have to make sure we don't loop back to the head of the list,
187 * which will happen if the entry is NOT on the list.
188 */
189
190 while (pEntry && (pEntry != &pList->ListHead)) {
191 if (pEntry == pEntryToFind) {
192 fFound = true;
193 break;
194 }
195 pEntry = pEntry->next;
196 }
197
198 }
199 return fFound;
200 }
201
csr_ll_open(tDblLinkList * pList)202 QDF_STATUS csr_ll_open(tDblLinkList *pList)
203 {
204 QDF_STATUS status = QDF_STATUS_SUCCESS;
205 QDF_STATUS qdf_status;
206
207 if (!pList) {
208 sme_err("Error!! pList is Null");
209 return QDF_STATUS_E_FAILURE;
210 }
211
212 if (LIST_FLAG_OPEN != pList->Flag) {
213 pList->Count = 0;
214 qdf_status = qdf_mutex_create(&pList->Lock);
215
216 if (QDF_IS_STATUS_SUCCESS(qdf_status)) {
217 csr_list_init(&pList->ListHead);
218 pList->Flag = LIST_FLAG_OPEN;
219 } else
220 status = QDF_STATUS_E_FAILURE;
221 }
222 return status;
223 }
224
csr_ll_close(tDblLinkList * pList)225 void csr_ll_close(tDblLinkList *pList)
226 {
227 if (!pList) {
228 sme_err("Error!! pList is Null");
229 return;
230 }
231
232 if (LIST_FLAG_OPEN == pList->Flag) {
233 /* Make sure the list is empty... */
234 csr_ll_purge(pList, LL_ACCESS_LOCK);
235 qdf_mutex_destroy(&pList->Lock);
236 pList->Flag = LIST_FLAG_CLOSE;
237 }
238 }
239
csr_ll_insert_tail(tDblLinkList * pList,tListElem * pEntry,bool fInterlocked)240 void csr_ll_insert_tail(tDblLinkList *pList, tListElem *pEntry,
241 bool fInterlocked)
242 {
243 if (!pList) {
244 sme_err("Error!! pList is Null");
245 return;
246 }
247
248 if (LIST_FLAG_OPEN == pList->Flag) {
249 if (fInterlocked)
250 csr_ll_lock(pList);
251
252 csr_list_insert_tail(&pList->ListHead, pEntry);
253 pList->Count++;
254 if (fInterlocked)
255 csr_ll_unlock(pList);
256 }
257 }
258
csr_ll_insert_head(tDblLinkList * pList,tListElem * pEntry,bool fInterlocked)259 void csr_ll_insert_head(tDblLinkList *pList, tListElem *pEntry,
260 bool fInterlocked)
261 {
262
263 if (!pList) {
264 sme_err("Error!! pList is Null");
265 return;
266 }
267
268 if (LIST_FLAG_OPEN == pList->Flag) {
269 if (fInterlocked)
270 csr_ll_lock(pList);
271
272 csr_list_insert_head(&pList->ListHead, pEntry);
273 pList->Count++;
274 if (fInterlocked)
275 csr_ll_unlock(pList);
276 }
277 }
278
csr_ll_insert_entry(tDblLinkList * pList,tListElem * pEntry,tListElem * pNewEntry,bool fInterlocked)279 void csr_ll_insert_entry(tDblLinkList *pList, tListElem *pEntry,
280 tListElem *pNewEntry, bool fInterlocked)
281 {
282 if (!pList) {
283 sme_err("Error!! pList is Null");
284 return;
285 }
286
287 if (LIST_FLAG_OPEN == pList->Flag) {
288 if (fInterlocked)
289 csr_ll_lock(pList);
290
291 csr_list_insert_entry(pEntry, pNewEntry);
292 pList->Count++;
293 if (fInterlocked)
294 csr_ll_unlock(pList);
295 }
296 }
297
csr_ll_remove_tail(tDblLinkList * pList,bool fInterlocked)298 tListElem *csr_ll_remove_tail(tDblLinkList *pList, bool fInterlocked)
299 {
300 tListElem *pEntry = NULL;
301
302 if (!pList) {
303 sme_err("Error!! pList is Null");
304 return pEntry;
305 }
306
307 if (LIST_FLAG_OPEN == pList->Flag) {
308 if (fInterlocked)
309 csr_ll_lock(pList);
310
311 if (!csrIsListEmpty(&pList->ListHead)) {
312 pEntry = csr_list_remove_tail(&pList->ListHead);
313 pList->Count--;
314 }
315 if (fInterlocked)
316 csr_ll_unlock(pList);
317 }
318
319 return pEntry;
320 }
321
csr_ll_peek_tail(tDblLinkList * pList,bool fInterlocked)322 tListElem *csr_ll_peek_tail(tDblLinkList *pList, bool fInterlocked)
323 {
324 tListElem *pEntry = NULL;
325
326 if (!pList) {
327 sme_err("Error!! pList is Null");
328 return pEntry;
329 }
330
331 if (LIST_FLAG_OPEN == pList->Flag) {
332 if (fInterlocked)
333 csr_ll_lock(pList);
334
335 if (!csrIsListEmpty(&pList->ListHead))
336 pEntry = pList->ListHead.last;
337
338 if (fInterlocked)
339 csr_ll_unlock(pList);
340 }
341
342 return pEntry;
343 }
344
csr_ll_remove_head(tDblLinkList * pList,bool fInterlocked)345 tListElem *csr_ll_remove_head(tDblLinkList *pList, bool fInterlocked)
346 {
347 tListElem *pEntry = NULL;
348
349 if (!pList) {
350 sme_err("Error!! pList is Null");
351 return pEntry;
352 }
353
354 if (LIST_FLAG_OPEN == pList->Flag) {
355 if (fInterlocked)
356 csr_ll_lock(pList);
357
358 if (!csrIsListEmpty(&pList->ListHead)) {
359 pEntry = csr_list_remove_head(&pList->ListHead);
360 pList->Count--;
361 }
362
363 if (fInterlocked)
364 csr_ll_unlock(pList);
365 }
366
367 return pEntry;
368 }
369
csr_ll_peek_head(tDblLinkList * pList,bool fInterlocked)370 tListElem *csr_ll_peek_head(tDblLinkList *pList, bool fInterlocked)
371 {
372 tListElem *pEntry = NULL;
373
374 if (!pList) {
375 sme_err("Error!! pList is Null");
376 return pEntry;
377 }
378
379 if (LIST_FLAG_OPEN == pList->Flag) {
380 if (fInterlocked)
381 csr_ll_lock(pList);
382
383 if (!csrIsListEmpty(&pList->ListHead))
384 pEntry = pList->ListHead.next;
385
386 if (fInterlocked)
387 csr_ll_unlock(pList);
388 }
389
390 return pEntry;
391 }
392
csr_ll_purge(tDblLinkList * pList,bool fInterlocked)393 void csr_ll_purge(tDblLinkList *pList, bool fInterlocked)
394 {
395 tListElem *pEntry;
396
397 if (!pList) {
398 sme_err("Error!! pList is Null");
399 return;
400 }
401
402 if (LIST_FLAG_OPEN == pList->Flag) {
403 if (fInterlocked)
404 csr_ll_lock(pList);
405
406 /* Remove everything from the list */
407 while ((pEntry = csr_ll_remove_head(pList, LL_ACCESS_NOLOCK)))
408 ;
409
410 if (fInterlocked)
411 csr_ll_unlock(pList);
412 }
413 }
414
csr_ll_remove_entry(tDblLinkList * pList,tListElem * pEntryToRemove,bool fInterlocked)415 bool csr_ll_remove_entry(tDblLinkList *pList, tListElem *pEntryToRemove,
416 bool fInterlocked)
417 {
418 bool fFound = false;
419 tListElem *pEntry;
420
421 if (!pList) {
422 sme_err("Error!! pList is Null");
423 return fFound;
424 }
425
426 if (LIST_FLAG_OPEN == pList->Flag) {
427 if (fInterlocked)
428 csr_ll_lock(pList);
429
430 pEntry = csr_ll_peek_head(pList, LL_ACCESS_NOLOCK);
431
432 /* Have to make sure we don't loop back to the head of the
433 * list, which will happen if the entry is NOT on the list.
434 */
435 while (pEntry && (pEntry != &pList->ListHead)) {
436 if (pEntry == pEntryToRemove) {
437 csr_list_remove_entry(pEntry);
438 pList->Count--;
439
440 fFound = true;
441 break;
442 }
443
444 pEntry = pEntry->next;
445 }
446 if (fInterlocked)
447 csr_ll_unlock(pList);
448 }
449
450 return fFound;
451 }
452
csr_ll_next(tDblLinkList * pList,tListElem * pEntry,bool fInterlocked)453 tListElem *csr_ll_next(tDblLinkList *pList, tListElem *pEntry,
454 bool fInterlocked)
455 {
456 tListElem *pNextEntry = NULL;
457
458 if (!pList) {
459 sme_err("Error!! pList is Null");
460 return pNextEntry;
461 }
462
463 if (LIST_FLAG_OPEN == pList->Flag) {
464 if (fInterlocked)
465 csr_ll_lock(pList);
466
467 if (!csrIsListEmpty(&pList->ListHead)
468 && csr_ll_find_entry(pList, pEntry)) {
469 pNextEntry = pEntry->next;
470 /* Make sure we don't walk past the head */
471 if (pNextEntry == &pList->ListHead)
472 pNextEntry = NULL;
473 }
474
475 if (fInterlocked)
476 csr_ll_unlock(pList);
477 }
478
479 return pNextEntry;
480 }
481
csr_ll_previous(tDblLinkList * pList,tListElem * pEntry,bool fInterlocked)482 tListElem *csr_ll_previous(tDblLinkList *pList, tListElem *pEntry,
483 bool fInterlocked)
484 {
485 tListElem *pNextEntry = NULL;
486
487 if (!pList) {
488 sme_err("Error!! pList is Null");
489 return pNextEntry;
490 }
491
492 if (LIST_FLAG_OPEN == pList->Flag) {
493 if (fInterlocked)
494 csr_ll_lock(pList);
495
496 if (!csrIsListEmpty(&pList->ListHead)
497 && csr_ll_find_entry(pList, pEntry)) {
498 pNextEntry = pEntry->last;
499 /* Make sure we don't walk past the head */
500 if (pNextEntry == &pList->ListHead)
501 pNextEntry = NULL;
502 }
503
504 if (fInterlocked)
505 csr_ll_unlock(pList);
506 }
507
508 return pNextEntry;
509 }
510