1 /** \file siteHash.c
2 * \brief Site Hash implementation
3 *
4 * \see siteHash.h
5 */
6 /****************************************************************************
7 **+-----------------------------------------------------------------------+**
8 **| |**
9 **| Copyright(c) 1998 - 2008 Texas Instruments. All rights reserved. |**
10 **| All rights reserved. |**
11 **| |**
12 **| Redistribution and use in source and binary forms, with or without |**
13 **| modification, are permitted provided that the following conditions |**
14 **| are met: |**
15 **| |**
16 **| * Redistributions of source code must retain the above copyright |**
17 **| notice, this list of conditions and the following disclaimer. |**
18 **| * Redistributions in binary form must reproduce the above copyright |**
19 **| notice, this list of conditions and the following disclaimer in |**
20 **| the documentation and/or other materials provided with the |**
21 **| distribution. |**
22 **| * Neither the name Texas Instruments nor the names of its |**
23 **| contributors may be used to endorse or promote products derived |**
24 **| from this software without specific prior written permission. |**
25 **| |**
26 **| THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS |**
27 **| "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT |**
28 **| LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR |**
29 **| A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT |**
30 **| OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, |**
31 **| SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT |**
32 **| LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, |**
33 **| DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY |**
34 **| THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT |**
35 **| (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE |**
36 **| OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. |**
37 **| |**
38 **+-----------------------------------------------------------------------+**
39 ****************************************************************************/
40
41 /****************************************************************************/
42 /* */
43 /* MODULE: siteHash.c */
44 /* PURPOSE: Site Hash implementation */
45 /* */
46 /***************************************************************************/
47 #include "report.h"
48 #include "osTIType.h"
49 #include "osApi.h"
50 #include "siteMgrApi.h"
51 #include "siteHash.h"
52 #include "smeApi.h"
53 #include "utils.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: 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 os_memoryZero(pSiteMgr->hOs, &pSiteTableParams->siteTable[0], sizeof(siteEntry_t)*pSiteTableParams->maxNumOfSites);
98
99 for (i = 0; i < pSiteTableParams->maxNumOfSites; i++)
100 {
101 pSiteTableParams->siteTable[i].index = i;
102 pSiteTableParams->siteTable[i].siteType = SITE_NULL;
103 pSiteTableParams->siteTable[i].beaconRecv = FALSE;
104 pSiteTableParams->siteTable[i].beaconReceiveAfterJoin = TRUE;
105 pSiteTableParams->siteTable[i].dtimPeriod = 1;
106 }
107
108 pSiteTableParams->numOfSites = 0;
109
110 pSiteMgr->pSitesMgmtParams->pPrimarySite = NULL;
111
112 return OK;
113 }
114
115 /************************************************************************
116 * siteMgr_removeNotReceivedSites *
117 ************************************************************************
118 DESCRIPTION:
119
120 INPUT:
121
122 OUTPUT:
123
124 RETURN: OK
125
126 ************************************************************************/
127
siteMgr_removeNotReceivedSites(TI_HANDLE hSiteMgr)128 TI_STATUS siteMgr_removeNotReceivedSites(TI_HANDLE hSiteMgr)
129 {
130 UINT8 siteIndex, tableIndex;
131 siteEntry_t *pSiteEntry;
132 siteMgr_t *pSiteMgr = (siteMgr_t *)hSiteMgr;
133
134 siteTablesParams_t* currTable = pSiteMgr->pSitesMgmtParams->pCurrentSiteTable;
135
136 for (tableIndex = 0; tableIndex < NUM_OF_SITE_TABLE ; tableIndex++)
137 {
138 for (siteIndex = 0; siteIndex < currTable->maxNumOfSites; siteIndex++)
139 {
140 pSiteEntry = &(currTable->siteTable[siteIndex]);
141
142 /* Self site & null site are never aged out. */
143 if ((pSiteEntry->siteType == SITE_SELF) || (pSiteEntry->siteType == SITE_NULL))
144 continue;
145
146 if(pSiteEntry->Not_Received > WLAN_NUM_OF_MISSED_SACNS_BEFORE_AGING)
147 removeSiteEntry(pSiteMgr, currTable, pSiteEntry);
148 }
149
150 /* change the current site table */
151 if(currTable == &pSiteMgr->pSitesMgmtParams->dot11BG_sitesTables)
152 currTable = (siteTablesParams_t *)&pSiteMgr->pSitesMgmtParams->dot11A_sitesTables;
153 else
154 currTable = &pSiteMgr->pSitesMgmtParams->dot11BG_sitesTables;
155
156 }
157 return OK;
158 }
159
160 /************************************************************************
161 * findSiteEntry *
162 ************************************************************************
163 DESCRIPTION: Perform the following things:
164 - Compute the site's hash entry based on the site BSSID and hash function
165 - Look fotr the site entry in the linked list pointed by the hash entry
166 - If the site is found in the site table, returns a pointer to the site entry
167 - If the site is not found, return NULL.
168
169 INPUT: pSiteMgr - Handle to site mgr
170 mac - The site BSSID
171
172
173 OUTPUT:
174
175 RETURN: Pointer to the site entry if site found, NULL otherwise
176
177 ************************************************************************/
findSiteEntry(siteMgr_t * pSiteMgr,macAddress_t * mac)178 siteEntry_t *findSiteEntry(siteMgr_t *pSiteMgr,
179 macAddress_t *mac)
180 {
181 siteTablesParams_t *pCurrentSiteTable = pSiteMgr->pSitesMgmtParams->pCurrentSiteTable;
182 siteEntry_t *pSiteEntry;
183 UINT8 tableIndex=2, i;
184
185
186 do
187 {
188 tableIndex--;
189 for (i = 0; i < pCurrentSiteTable->maxNumOfSites; i++)
190 {
191 pSiteEntry = &(pCurrentSiteTable->siteTable[i]);
192
193 if MAC_EQUAL((&(pSiteEntry->bssid)), mac)
194 {
195 WLAN_REPORT_INFORMATION(pSiteMgr->hReport, SITE_UPDATE_MODULE_LOG, ("FIND success, bssid: %X-%X-%X-%X-%X-%X\n\n", mac->addr[0], mac->addr[1], mac->addr[2], mac->addr[3], mac->addr[4], mac->addr[5]));
196 return pSiteEntry;
197 }
198
199 }
200 if ((pSiteMgr->pDesiredParams->siteMgrDesiredDot11Mode == DOT11_DUAL_MODE) && (tableIndex==1))
201 { /* change site table */
202 if (pCurrentSiteTable == &pSiteMgr->pSitesMgmtParams->dot11BG_sitesTables)
203 {
204 pCurrentSiteTable = (siteTablesParams_t *)&pSiteMgr->pSitesMgmtParams->dot11A_sitesTables;
205 }
206 else
207 {
208 pCurrentSiteTable = &pSiteMgr->pSitesMgmtParams->dot11BG_sitesTables;
209 }
210 }
211
212 } while (tableIndex>0);
213
214
215
216 WLAN_REPORT_INFORMATION(pSiteMgr->hReport, SITE_UPDATE_MODULE_LOG,
217 ("FIND failure, bssid: %X-%X-%X-%X-%X-%X\n\n", mac->addr[0], mac->addr[1], mac->addr[2], mac->addr[3], mac->addr[4], mac->addr[5]));
218
219
220 return NULL;
221 }
222
223 /************************************************************************
224 * findAndInsertSiteEntry *
225 ************************************************************************
226 DESCRIPTION: Perform the following things:
227 - Compute the site's hash entry based on the site BSSID and hash function
228 - Look for the site entry in the linked list pointed by the hash entry
229 - If the site is found in the site table, returns a pointer to the site entry
230 - If the site is not found in the site table, tries to add the site
231 - If succeeds, returns a pointer to the site entry
232 - Otherwise, returns NULL
233
234 INPUT: pSiteMgr - Handle to site mgr
235 mac - The site BSSID
236 band - The site band
237
238
239 OUTPUT:
240
241 RETURN: Pointer to the site entry if site found/inserted, NULL otherwise
242
243 ************************************************************************/
findAndInsertSiteEntry(siteMgr_t * pSiteMgr,macAddress_t * mac,radioBand_e band)244 siteEntry_t *findAndInsertSiteEntry(siteMgr_t *pSiteMgr,
245 macAddress_t *mac,
246 radioBand_e band)
247 {
248 UINT8 i, emptySiteIndex=0, nextSite2Remove=0;
249 siteEntry_t *pSiteEntry, *pPrimarySite=pSiteMgr->pSitesMgmtParams->pPrimarySite;
250 sitesMgmtParams_t *pSitesMgmtParams = pSiteMgr->pSitesMgmtParams;
251 siteTablesParams_t *pCurrentSiteTable;
252 BOOL firstEmptySiteFound = FALSE;
253 UINT32 oldestTS;
254
255
256 /* choose site table according to AP's band */
257 if ( RADIO_BAND_2_4_GHZ == band )
258 {
259 pCurrentSiteTable = &(pSitesMgmtParams->dot11BG_sitesTables);
260 }
261 else if (RADIO_BAND_5_0_GHZ == band)
262 {
263 pCurrentSiteTable = (siteTablesParams_t*) &(pSitesMgmtParams->dot11A_sitesTables);
264 }
265 else
266 {
267 WLAN_REPORT_ERROR(pSiteMgr->hReport, SITE_UPDATE_MODULE_LOG, ("Bad band: %d\n\n", band));
268 pCurrentSiteTable = &(pSitesMgmtParams->dot11BG_sitesTables);
269 }
270
271 /* Set the first TS to a site which is not the Primary site */
272 if (pPrimarySite != &(pCurrentSiteTable->siteTable[0]))
273 {
274 oldestTS = pCurrentSiteTable->siteTable[0].localTimeStamp;
275 }
276 else
277 {
278 oldestTS = pCurrentSiteTable->siteTable[1].localTimeStamp;
279 }
280
281 /* Loop all the sites till the desired MAC is found */
282 for (i = 0; i < pCurrentSiteTable->maxNumOfSites; i++)
283 {
284 pSiteEntry = &(pCurrentSiteTable->siteTable[i]);
285
286 if MAC_EQUAL((&(pSiteEntry->bssid)), mac)
287 {
288
289 WLAN_REPORT_INFORMATION(pSiteMgr->hReport, SITE_UPDATE_MODULE_LOG, ("FIND success, bssid: %X-%X-%X-%X-%X-%X\n\n", mac->addr[0], mac->addr[1], mac->addr[2], mac->addr[3], mac->addr[4], mac->addr[5]));
290
291 return pSiteEntry;
292 }
293 else if (pSiteEntry->siteType == SITE_NULL)
294 { /* Save the first empty site, in case the
295 desired MAC is not found */
296 if (!firstEmptySiteFound)
297 {
298 emptySiteIndex = i;
299 firstEmptySiteFound=TRUE;
300 }
301
302 }
303 if ((oldestTS > pSiteEntry->localTimeStamp) &&
304 (pSiteEntry != pPrimarySite))
305 { /* Save the oldest site's index, according to TS */
306 oldestTS = pSiteEntry->localTimeStamp;
307 nextSite2Remove = i;
308 }
309 }
310
311
312 if ((!firstEmptySiteFound) || (pCurrentSiteTable->numOfSites>=pCurrentSiteTable->maxNumOfSites))
313 {
314 /* No NULL entry has been found. Remove the oldest site */
315 pSiteEntry = &(pCurrentSiteTable->siteTable[nextSite2Remove]);
316 WLAN_REPORT_INFORMATION(pSiteMgr->hReport, SITE_UPDATE_MODULE_LOG,
317 ("INSERT failure, no free entry!, numOfSites=%d, removing site index=%d,\n \
318 bssid: %X-%X-%X-%X-%X-%X, ts=%d \n",
319 pCurrentSiteTable->numOfSites, nextSite2Remove,
320 pSiteEntry->bssid.addr[0], pSiteEntry->bssid.addr[1], pSiteEntry->bssid.addr[2],
321 pSiteEntry->bssid.addr[3], pSiteEntry->bssid.addr[4], pSiteEntry->bssid.addr[5],
322 pSiteEntry->localTimeStamp));
323 removeSiteEntry(pSiteMgr, pCurrentSiteTable, pSiteEntry);
324 emptySiteIndex = nextSite2Remove;
325
326 }
327
328
329 pCurrentSiteTable->numOfSites++;
330
331 pSiteEntry = &(pCurrentSiteTable->siteTable[emptySiteIndex]);
332
333 /* fill the entry with the station mac */
334 MAC_COPY(pSiteMgr->hOs, (&(pSiteEntry->bssid)), mac);
335
336 /* Some parameters have to be initialized immediately after entry allocation */
337 /* We set fourXsupported for each site to TRUE,
338 It will be set to FALSE only if ProbeResponse without 4x IE
339 will be received for any specific site.
340 It is done in this way to ensure that even if the STA didn't receive
341 ProbeResponse from TI AP (received only Beacons), the AssociationReq
342 sent by the STA will include 4x IE */
343 pSiteEntry->fourXsupported = TRUE;
344
345 if(pSiteMgr->siteMgrOperationalMode == DOT11_G_MODE)
346 pSiteEntry->currentSlotTime = pSiteMgr->pDesiredParams->siteMgrDesiredSlotTime;
347
348 WLAN_REPORT_INFORMATION(pSiteMgr->hReport, SITE_UPDATE_MODULE_LOG,
349 ("INSERT success, bssid: %X-%X-%X-%X-%X-%X, band=%d, index=%d\n\n",
350 mac->addr[0], mac->addr[1], mac->addr[2], mac->addr[3], mac->addr[4], mac->addr[5],
351 band, emptySiteIndex));
352
353
354 return pSiteEntry;
355 }
356
357 /************************************************************************
358 * removeSiteEntry *
359 ************************************************************************
360 DESCRIPTION: Removes the site entry from the site table
361
362 INPUT: pSiteMgr - Handle to site mgr
363 pCurrSiteTblParams - Pointer to current site table parameters
364 hashPtr - Pointer to the site entry
365
366
367 OUTPUT:
368
369 RETURN:
370
371 ************************************************************************/
removeSiteEntry(siteMgr_t * pSiteMgr,siteTablesParams_t * pCurrSiteTblParams,siteEntry_t * pSiteEntry)372 void removeSiteEntry(siteMgr_t *pSiteMgr,
373 siteTablesParams_t *pCurrSiteTblParams,
374 siteEntry_t *pSiteEntry)
375 {
376 UINT8 index;
377
378 if (pSiteEntry == NULL)
379 {
380 WLAN_REPORT_ERROR(pSiteMgr->hReport, SITE_MGR_MODULE_LOG, ("REMOVAL failure, site is NULL\n\n"));
381 return;
382 }
383
384 if (pCurrSiteTblParams->numOfSites == 0)
385 {
386 WLAN_REPORT_ERROR(pSiteMgr->hReport, SITE_MGR_MODULE_LOG, ("REMOVAL failure, site table is empty\n\n"));
387 return;
388 }
389
390 WLAN_REPORT_INFORMATION(pSiteMgr->hReport, SITE_MGR_MODULE_LOG, ("removeSiteEntry REMOVE ssid=%s, bssid= 0x%x-0x%x-0x%x-0x%x-0x%x-0x%x\n\n",
391 pSiteEntry->ssid.ssidString,
392 pSiteEntry->bssid.addr[0], pSiteEntry->bssid.addr[1], pSiteEntry->bssid.addr[2],
393 pSiteEntry->bssid.addr[3], pSiteEntry->bssid.addr[4], pSiteEntry->bssid.addr[5] ));
394
395 pCurrSiteTblParams->numOfSites--;
396
397 /* Now remove (exclude) hashPtr entry from the linked list */
398
399 WLAN_REPORT_INFORMATION(pSiteMgr->hReport, SITE_MGR_MODULE_LOG, ("REMOVAL success, bssid: %X-%X-%X-%X-%X-%X\n\n", pSiteEntry->bssid.addr[0], pSiteEntry->bssid.addr[1], pSiteEntry->bssid.addr[2], pSiteEntry->bssid.addr[3], pSiteEntry->bssid.addr[4], pSiteEntry->bssid.addr[5]));
400 WLAN_REPORT_INFORMATION(pSiteMgr->hReport, SITE_MGR_MODULE_LOG, (" SITE TABLE remaining entries number %d \n", pCurrSiteTblParams->numOfSites));
401
402 /* Clean the rest of the entry structure */
403 index = pSiteEntry->index; /* keep the index of the siteTable entry */
404 os_memoryZero(pSiteMgr->hOs, pSiteEntry, sizeof(siteEntry_t));
405
406 /* This is not required!!!! - Remove!!*/
407 pSiteEntry->dtimPeriod = 1;
408 pSiteEntry->siteType = SITE_NULL;
409 pSiteEntry->index = index; /* restore the index of the siteTable */
410
411 /* if removing previous primary site - update the link */
412 if (pSiteEntry == pSiteMgr->pSitesMgmtParams->pPrevPrimarySite)
413 {
414 pSiteMgr->pSitesMgmtParams->pPrevPrimarySite = NULL;
415 }
416
417 return;
418 }
419
420