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 ************************************************************************/ 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 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 ************************************************************************/ 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 ************************************************************************/ 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 ************************************************************************/ 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