1 /*
2 * siteHash.c
3 *
4 * Copyright(c) 1998 - 2009 Texas Instruments. All rights reserved.
5 * All rights reserved.
6 *
7 * Redistribution and use in source and binary forms, with or without
8 * modification, are permitted provided that the following conditions
9 * are met:
10 *
11 * * Redistributions of source code must retain the above copyright
12 * notice, this list of conditions and the following disclaimer.
13 * * Redistributions in binary form must reproduce the above copyright
14 * notice, this list of conditions and the following disclaimer in
15 * the documentation and/or other materials provided with the
16 * distribution.
17 * * Neither the name Texas Instruments nor the names of its
18 * contributors may be used to endorse or promote products derived
19 * from this software without specific prior written permission.
20 *
21 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
22 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
23 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
24 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
25 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
26 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
27 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
28 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
29 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
30 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
31 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
32 */
33
34 /** \file siteHash.c
35 * \brief Site Hash implementation
36 *
37 * \see siteHash.h
38 */
39
40 /****************************************************************************/
41 /* */
42 /* MODULE: siteHash.c */
43 /* PURPOSE: Site Hash implementation */
44 /* */
45 /***************************************************************************/
46
47 #define __FILE_ID__ FILE_ID_84
48 #include "tidef.h"
49 #include "report.h"
50 #include "osApi.h"
51 #include "siteMgrApi.h"
52 #include "siteHash.h"
53 #include "smeApi.h"
54
55
56 /****************************************************************************************************************
57
58 This file implements the site hash mechanism. This mechanism is used for faster access to the sites information.
59 It is compound of the following:
60 1. hash function - which maps the 4 last bits of the BSSID to an entry in the hash table.
61 2. hash table - each entry in the table points to a linked list of site entries
62 3. site table - each entry holds a site information
63
64 In order to find a site in the site table, we operate the hash function on the site's BSSID.
65 We receive a hash entry. We go over the linked list pointed by this hash entry until we find the site entry.
66 *****************************************************************************************************************/
67
68 #define WLAN_NUM_OF_MISSED_SACNS_BEFORE_AGING 2
69
70
71 /********************************************/
72 /* Functions Implementations */
73 /********************************************/
74 /************************************************************************
75 * siteMgr_resetSiteTable *
76 ************************************************************************
77 DESCRIPTION: reset the following things:
78 - Mgmt parameters structure
79 - Site table
80 - Hash table
81 - Primary site pointer
82 - Number of sites
83
84 INPUT: hSiteMgr - Handle to site mgr
85
86
87 OUTPUT:
88
89 RETURN: TI_OK
90
91 ************************************************************************/
siteMgr_resetSiteTable(TI_HANDLE hSiteMgr,siteTablesParams_t * pSiteTableParams)92 TI_STATUS siteMgr_resetSiteTable(TI_HANDLE hSiteMgr, siteTablesParams_t *pSiteTableParams)
93 {
94 int i;
95 siteMgr_t *pSiteMgr = (siteMgr_t *)hSiteMgr;
96
97 /* It looks like it never happens. Anyway decided to check */
98 if ( pSiteTableParams->maxNumOfSites > MAX_SITES_BG_BAND )
99 {
100 TRACE2( pSiteMgr->hReport, REPORT_SEVERITY_ERROR,
101 "siteMgr_resetSiteTable. pScanMngr->currentBSSBand=%d exceeds the limit %d\n",
102 pSiteTableParams->maxNumOfSites, MAX_SITES_BG_BAND);
103 handleRunProblem(PROBLEM_BUF_SIZE_VIOLATION);
104 return TI_NOK;
105 }
106 os_memoryZero(pSiteMgr->hOs, &pSiteTableParams->siteTable[0], sizeof(siteEntry_t)*pSiteTableParams->maxNumOfSites);
107
108 for (i = 0; i < pSiteTableParams->maxNumOfSites; i++)
109 {
110 pSiteTableParams->siteTable[i].index = i;
111 pSiteTableParams->siteTable[i].siteType = SITE_NULL;
112 pSiteTableParams->siteTable[i].beaconRecv = TI_FALSE;
113 pSiteTableParams->siteTable[i].dtimPeriod = 1;
114 }
115
116 pSiteTableParams->numOfSites = 0;
117
118 pSiteMgr->pSitesMgmtParams->pPrimarySite = NULL;
119
120 return TI_OK;
121 }
122
123 /************************************************************************
124 * findSiteEntry *
125 ************************************************************************
126 DESCRIPTION: Perform the following things:
127 - Compute the site's hash entry based on the site BSSID and hash function
128 - Look fotr the site entry in the linked list pointed by the hash entry
129 - If the site is found in the site table, returns a pointer to the site entry
130 - If the site is not found, return NULL.
131
132 INPUT: pSiteMgr - Handle to site mgr
133 mac - The site BSSID
134
135
136 OUTPUT:
137
138 RETURN: Pointer to the site entry if site found, NULL otherwise
139
140 ************************************************************************/
findSiteEntry(siteMgr_t * pSiteMgr,TMacAddr * mac)141 siteEntry_t *findSiteEntry(siteMgr_t *pSiteMgr,
142 TMacAddr *mac)
143 {
144 siteTablesParams_t *pCurrentSiteTable = pSiteMgr->pSitesMgmtParams->pCurrentSiteTable;
145 siteEntry_t *pSiteEntry;
146 TI_UINT8 tableIndex=2, i;
147
148 /* It looks like it never happens. Anyway decided to check */
149 if ( pCurrentSiteTable->maxNumOfSites > MAX_SITES_BG_BAND )
150 {
151 TRACE2( pSiteMgr->hReport, REPORT_SEVERITY_ERROR,
152 "findSiteEntry. pCurrentSiteTable->maxNumOfSites=%d exceeds the limit %d\n",
153 pCurrentSiteTable->maxNumOfSites, MAX_SITES_BG_BAND);
154 handleRunProblem(PROBLEM_BUF_SIZE_VIOLATION);
155 return NULL;
156 }
157
158 do
159 {
160 tableIndex--;
161 for (i = 0; i < pCurrentSiteTable->maxNumOfSites; i++)
162 {
163 pSiteEntry = &(pCurrentSiteTable->siteTable[i]);
164
165 if (MAC_EQUAL (pSiteEntry->bssid, *mac))
166 {
167 TRACE6(pSiteMgr->hReport, REPORT_SEVERITY_INFORMATION,
168 "FIND success, bssid: %X-%X-%X-%X-%X-%X\n\n", (*mac)[0], (*mac)[1], (*mac)[2], (*mac)[3], (*mac)[4], (*mac)[5]);
169 return pSiteEntry;
170 }
171
172 }
173 if ((pSiteMgr->pDesiredParams->siteMgrDesiredDot11Mode == DOT11_DUAL_MODE) &&
174 (tableIndex==1))
175 { /* change site table */
176 if (pCurrentSiteTable == &pSiteMgr->pSitesMgmtParams->dot11BG_sitesTables)
177 {
178 pCurrentSiteTable = (siteTablesParams_t *)&pSiteMgr->pSitesMgmtParams->dot11A_sitesTables;
179 }
180 else
181 {
182 pCurrentSiteTable = &pSiteMgr->pSitesMgmtParams->dot11BG_sitesTables;
183 }
184 }
185
186 } while (tableIndex>0);
187
188
189
190 TRACE6(pSiteMgr->hReport, REPORT_SEVERITY_INFORMATION, "FIND failure, bssid: %X-%X-%X-%X-%X-%X\n\n", (*mac)[0], (*mac)[1], (*mac)[2], (*mac)[3], (*mac)[4], (*mac)[5]);
191
192
193 return NULL;
194 }
195
196 /************************************************************************
197 * findAndInsertSiteEntry *
198 ************************************************************************
199 DESCRIPTION: Perform the following things:
200 - Compute the site's hash entry based on the site BSSID and hash function
201 - Look for the site entry in the linked list pointed by the hash entry
202 - If the site is found in the site table, returns a pointer to the site entry
203 - If the site is not found in the site table, tries to add the site
204 - If succeeds, returns a pointer to the site entry
205 - Otherwise, returns NULL
206
207 INPUT: pSiteMgr - Handle to site mgr
208 mac - The site BSSID
209 band - The site band
210
211
212 OUTPUT:
213
214 RETURN: Pointer to the site entry if site found/inserted, NULL otherwise
215
216 ************************************************************************/
findAndInsertSiteEntry(siteMgr_t * pSiteMgr,TMacAddr * mac,ERadioBand band)217 siteEntry_t *findAndInsertSiteEntry(siteMgr_t *pSiteMgr,
218 TMacAddr *mac,
219 ERadioBand band)
220 {
221 TI_UINT8 i, emptySiteIndex=0, nextSite2Remove=0;
222 siteEntry_t *pSiteEntry, *pPrimarySite=pSiteMgr->pSitesMgmtParams->pPrimarySite;
223 sitesMgmtParams_t *pSitesMgmtParams = pSiteMgr->pSitesMgmtParams;
224 siteTablesParams_t *pCurrentSiteTable;
225 TI_BOOL firstEmptySiteFound = TI_FALSE;
226 TI_UINT32 oldestTS;
227
228
229 /* choose site table according to AP's band */
230 if ( RADIO_BAND_2_4_GHZ == band )
231 {
232 pCurrentSiteTable = &(pSitesMgmtParams->dot11BG_sitesTables);
233 }
234 else if (RADIO_BAND_5_0_GHZ == band)
235 {
236 pCurrentSiteTable = (siteTablesParams_t*) &(pSitesMgmtParams->dot11A_sitesTables);
237 }
238 else
239 {
240 TRACE1(pSiteMgr->hReport, REPORT_SEVERITY_ERROR, "Bad band: %d\n\n", band);
241 pCurrentSiteTable = &(pSitesMgmtParams->dot11BG_sitesTables);
242 }
243
244 /* Set the first TS to a site which is not the Primary site */
245 if (pPrimarySite != &(pCurrentSiteTable->siteTable[0]))
246 {
247 oldestTS = pCurrentSiteTable->siteTable[0].localTimeStamp;
248 }
249 else
250 {
251 oldestTS = pCurrentSiteTable->siteTable[1].localTimeStamp;
252 }
253 /* It looks like it never happens. Anyway decided to check */
254 if ( pCurrentSiteTable->maxNumOfSites > MAX_SITES_BG_BAND )
255 {
256 TRACE2( pSiteMgr->hReport, REPORT_SEVERITY_ERROR,
257 "findAndInsertSiteEntry. pCurrentSiteTable->maxNumOfSites=%d exceeds the limit %d\n",
258 pCurrentSiteTable->maxNumOfSites, MAX_SITES_BG_BAND);
259 handleRunProblem(PROBLEM_BUF_SIZE_VIOLATION);
260 return NULL;
261 }
262 /* Loop all the sites till the desired MAC is found */
263 for (i = 0; i < pCurrentSiteTable->maxNumOfSites; i++)
264 {
265 pSiteEntry = &(pCurrentSiteTable->siteTable[i]);
266
267 if (MAC_EQUAL (pSiteEntry->bssid, *mac))
268 {
269
270 TRACE6(pSiteMgr->hReport, REPORT_SEVERITY_INFORMATION, "FIND success, bssid: %X-%X-%X-%X-%X-%X\n\n", (*mac)[0], (*mac)[1], (*mac)[2], (*mac)[3], (*mac)[4], (*mac)[5]);
271
272 return pSiteEntry;
273 }
274 else if (pSiteEntry->siteType == SITE_NULL)
275 { /* Save the first empty site, in case the
276 desired MAC is not found */
277 if (!firstEmptySiteFound)
278 {
279 emptySiteIndex = i;
280 firstEmptySiteFound=TI_TRUE;
281 }
282
283 }
284 else if (oldestTS == pSiteEntry->localTimeStamp)
285 { /* Save the oldest site's index, according to TS */
286 nextSite2Remove = i;
287 }
288 }
289
290 TRACE4(pSiteMgr->hReport, REPORT_SEVERITY_INFORMATION, "INSERT failure, no free entry!, oldestTS=%d, nextSite2Remove=%d, "
291 "[0].localTimeStamp=%d, [1]localTimeStamp%d \n",
292 oldestTS, nextSite2Remove,
293 pCurrentSiteTable->siteTable[0].localTimeStamp,
294 pCurrentSiteTable->siteTable[1].localTimeStamp);
295
296 if ((!firstEmptySiteFound) || (pCurrentSiteTable->numOfSites>=pCurrentSiteTable->maxNumOfSites))
297 {
298 /* No NULL entry has been found. Remove the oldest site */
299 pSiteEntry = &(pCurrentSiteTable->siteTable[nextSite2Remove]);
300 TRACE9(pSiteMgr->hReport, REPORT_SEVERITY_INFORMATION, "INSERT failure, no free entry!, numOfSites=%d, removing site index=%d,\n bssid: %X-%X-%X-%X-%X-%X, ts=%d \n", pCurrentSiteTable->numOfSites, nextSite2Remove, pSiteEntry->bssid[0], pSiteEntry->bssid[1], pSiteEntry->bssid[2], pSiteEntry->bssid[3], pSiteEntry->bssid[4], pSiteEntry->bssid[5], pSiteEntry->localTimeStamp);
301 removeSiteEntry(pSiteMgr, pCurrentSiteTable, pSiteEntry);
302 emptySiteIndex = nextSite2Remove;
303
304 }
305
306
307 pCurrentSiteTable->numOfSites++;
308
309 pSiteEntry = &(pCurrentSiteTable->siteTable[emptySiteIndex]);
310
311 /* fill the entry with the station mac */
312 MAC_COPY (pSiteEntry->bssid, *mac);
313
314 /* Some parameters have to be initialized immediately after entry allocation */
315
316 if(pSiteMgr->siteMgrOperationalMode == DOT11_G_MODE)
317 pSiteEntry->currentSlotTime = pSiteMgr->pDesiredParams->siteMgrDesiredSlotTime;
318
319 TRACE8(pSiteMgr->hReport, REPORT_SEVERITY_INFORMATION, "INSERT success, bssid: %X-%X-%X-%X-%X-%X, band=%d, index=%d\n\n", (*mac)[0], (*mac)[1], (*mac)[2], (*mac)[3], (*mac)[4], (*mac)[5], band, emptySiteIndex);
320
321
322 return pSiteEntry;
323 }
324
325 /************************************************************************
326 * removeSiteEntry *
327 ************************************************************************
328 DESCRIPTION: Removes the site entry from the site table
329
330 INPUT: pSiteMgr - Handle to site mgr
331 pCurrSiteTblParams - Pointer to current site table parameters
332 hashPtr - Pointer to the site entry
333
334
335 OUTPUT:
336
337 RETURN:
338
339 ************************************************************************/
removeSiteEntry(siteMgr_t * pSiteMgr,siteTablesParams_t * pCurrSiteTblParams,siteEntry_t * pSiteEntry)340 void removeSiteEntry(siteMgr_t *pSiteMgr,
341 siteTablesParams_t *pCurrSiteTblParams,
342 siteEntry_t *pSiteEntry)
343 {
344 TI_UINT8 index;
345
346 if (pSiteEntry == NULL)
347 {
348 TRACE0(pSiteMgr->hReport, REPORT_SEVERITY_ERROR, "REMOVAL failure, site is NULL\n\n");
349 return;
350 }
351
352 if (pCurrSiteTblParams->numOfSites == 0)
353 {
354 TRACE0(pSiteMgr->hReport, REPORT_SEVERITY_ERROR, "REMOVAL failure, site table is empty\n\n");
355 return;
356 }
357
358 TRACE6(pSiteMgr->hReport, REPORT_SEVERITY_INFORMATION, "removeSiteEntry REMOVE ssid=, bssid= 0x%x-0x%x-0x%x-0x%x-0x%x-0x%x\n\n", pSiteEntry->bssid[0], pSiteEntry->bssid[1], pSiteEntry->bssid[2], pSiteEntry->bssid[3], pSiteEntry->bssid[4], pSiteEntry->bssid[5] );
359
360 pCurrSiteTblParams->numOfSites--;
361
362 /* Now remove (exclude) hashPtr entry from the linked list */
363
364 TRACE6(pSiteMgr->hReport, REPORT_SEVERITY_INFORMATION, "REMOVAL success, bssid: %X-%X-%X-%X-%X-%X\n\n", pSiteEntry->bssid[0], pSiteEntry->bssid[1], pSiteEntry->bssid[2], pSiteEntry->bssid[3], pSiteEntry->bssid[4], pSiteEntry->bssid[5]);
365 TRACE1(pSiteMgr->hReport, REPORT_SEVERITY_INFORMATION, " SITE TABLE remaining entries number %d \n", pCurrSiteTblParams->numOfSites);
366
367 /* Clean the rest of the entry structure */
368 index = pSiteEntry->index; /* keep the index of the siteTable entry */
369 os_memoryZero(pSiteMgr->hOs, pSiteEntry, sizeof(siteEntry_t));
370
371 /* This is not required!!!! - Remove!!*/
372 pSiteEntry->dtimPeriod = 1;
373 pSiteEntry->siteType = SITE_NULL;
374 pSiteEntry->index = index; /* restore the index of the siteTable */
375
376 /* if removing previous primary site - update the link */
377 if (pSiteEntry == pSiteMgr->pSitesMgmtParams->pPrevPrimarySite)
378 {
379 pSiteMgr->pSitesMgmtParams->pPrevPrimarySite = NULL;
380 }
381
382 return;
383 }
384
385