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