drivers/uwb/allocator.c

   1 /*
   2  * UWB reservation management.
   3  *
   4  * Copyright (C) 2008 Cambridge Silicon Radio Ltd.
   5  *
   6  * This program is free software; you can redistribute it and/or
   7  * modify it under the terms of the GNU General Public License version
   8  * 2 as published by the Free Software Foundation.
   9  *
  10  * This program is distributed in the hope that it will be useful,
  11  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13  * GNU General Public License for more details.
  14  *
  15  * You should have received a copy of the GNU General Public License
  16  * along with this program.  If not, see <http://www.gnu.org/licenses/>.
  17  */
  18 #include <linux/kernel.h>
  19 #include <linux/slab.h>
  20 #include <linux/uwb.h>
  21
  22 #include "uwb-internal.h"
  23
  24 static void uwb_rsv_fill_column_alloc(struct uwb_rsv_alloc_info *ai)
  25 {
  26         int col, mas, safe_mas, unsafe_mas;
  27         unsigned char *bm = ai->bm;
  28         struct uwb_rsv_col_info *ci = ai->ci;
  29         unsigned char c;
  30
  31         for (col = ci->csi.start_col; col < UWB_NUM_ZONES; col += ci->csi.interval) {
  32
  33                 safe_mas   = ci->csi.safe_mas_per_col;
  34                 unsafe_mas = ci->csi.unsafe_mas_per_col;
  35
  36                 for (mas = 0; mas < UWB_MAS_PER_ZONE; mas++ ) {
  37                         if (bm[col * UWB_MAS_PER_ZONE + mas] == 0) {
  38
  39                                 if (safe_mas > 0) {
  40                                         safe_mas--;
  41                                         c = UWB_RSV_MAS_SAFE;
  42                                 } else if (unsafe_mas > 0) {
  43                                         unsafe_mas--;
  44                                         c = UWB_RSV_MAS_UNSAFE;
  45                                 } else {
  46                                         break;
  47                                 }
  48                                 bm[col * UWB_MAS_PER_ZONE + mas] = c;
  49                         }
  50                 }
  51         }
  52 }
  53
  54 static void uwb_rsv_fill_row_alloc(struct uwb_rsv_alloc_info *ai)
  55 {
  56         int mas, col, rows;
  57         unsigned char *bm = ai->bm;
  58         struct uwb_rsv_row_info *ri = &ai->ri;
  59         unsigned char c;
  60
  61         rows = 1;
  62         c = UWB_RSV_MAS_SAFE;
  63         for (mas = UWB_MAS_PER_ZONE - 1; mas >= 0; mas--) {
  64                 if (ri->avail[mas] == 1) {
  65
  66                         if (rows > ri->used_rows) {
  67                                 break;
  68                         } else if (rows > 7) {
  69                                 c = UWB_RSV_MAS_UNSAFE;
  70                         }
  71
  72                         for (col = 0; col < UWB_NUM_ZONES; col++) {
  73                                 if (bm[col * UWB_NUM_ZONES + mas] != UWB_RSV_MAS_NOT_AVAIL) {
  74                                         bm[col * UWB_NUM_ZONES + mas] = c;
  75                                         if(c == UWB_RSV_MAS_SAFE)
  76                                                 ai->safe_allocated_mases++;
  77                                         else
  78                                                 ai->unsafe_allocated_mases++;
  79                                 }
  80                         }
  81                         rows++;
  82                 }
  83         }
  84         ai->total_allocated_mases = ai->safe_allocated_mases + ai->unsafe_allocated_mases;
  85 }
  86
  87 /*
  88  * Find the best column set for a given availability, interval, num safe mas and
  89  * num unsafe mas.
  90  *
  91  * The different sets are tried in order as shown below, depending on the interval.
  92  *
  93  * interval = 16
  94  *      deep = 0
  95  *              set 1 ->  {  8 }
  96  *      deep = 1
  97  *              set 1 ->  {  4 }
  98  *              set 2 ->  { 12 }
  99  *      deep = 2
 100  *              set 1 ->  {  2 }
 101  *              set 2 ->  {  6 }
 102  *              set 3 ->  { 10 }
 103  *              set 4 ->  { 14 }
 104  *      deep = 3
 105  *              set 1 ->  {  1 }
 106  *              set 2 ->  {  3 }
 107  *              set 3 ->  {  5 }
 108  *              set 4 ->  {  7 }
 109  *              set 5 ->  {  9 }
 110  *              set 6 ->  { 11 }
 111  *              set 7 ->  { 13 }
 112  *              set 8 ->  { 15 }
 113  *
 114  * interval = 8
 115  *      deep = 0
 116  *              set 1 ->  {  4  12 }
 117  *      deep = 1
 118  *              set 1 ->  {  2  10 }
 119  *              set 2 ->  {  6  14 }
 120  *      deep = 2
 121  *              set 1 ->  {  1   9 }
 122  *              set 2 ->  {  3  11 }
 123  *              set 3 ->  {  5  13 }
 124  *              set 4 ->  {  7  15 }
 125  *
 126  * interval = 4
 127  *      deep = 0
 128  *              set 1 ->  {  2   6  10  14 }
 129  *      deep = 1
 130  *              set 1 ->  {  1   5   9  13 }
 131  *              set 2 ->  {  3   7  11  15 }
 132  *
 133  * interval = 2
 134  *      deep = 0
 135  *              set 1 ->  {  1   3   5   7   9  11  13  15 }
 136  */
 137 static int uwb_rsv_find_best_column_set(struct uwb_rsv_alloc_info *ai, int interval,
 138                                         int num_safe_mas, int num_unsafe_mas)
 139 {
 140         struct uwb_rsv_col_info *ci = ai->ci;
 141         struct uwb_rsv_col_set_info *csi = &ci->csi;
 142         struct uwb_rsv_col_set_info tmp_csi;
 143         int deep, set, col, start_col_deep, col_start_set;
 144         int start_col, max_mas_in_set, lowest_max_mas_in_deep;
 145         int n_mas;
 146         int found = UWB_RSV_ALLOC_NOT_FOUND;
 147
 148         tmp_csi.start_col = 0;
 149         start_col_deep = interval;
 150         n_mas = num_unsafe_mas + num_safe_mas;
 151
 152         for (deep = 0; ((interval >> deep) & 0x1) == 0; deep++) {
 153                 start_col_deep /= 2;
 154                 col_start_set = 0;
 155                 lowest_max_mas_in_deep = UWB_MAS_PER_ZONE;
 156
 157                 for (set = 1; set <= (1 << deep); set++) {
 158                         max_mas_in_set = 0;
 159                         start_col = start_col_deep + col_start_set;
 160                         for (col = start_col; col < UWB_NUM_ZONES; col += interval) {
 161
 162                                 if (ci[col].max_avail_safe >= num_safe_mas &&
 163                                     ci[col].max_avail_unsafe >= n_mas) {
 164                                         if (ci[col].highest_mas[n_mas] > max_mas_in_set)
 165                                                 max_mas_in_set = ci[col].highest_mas[n_mas];
 166                                 } else {
 167                                         max_mas_in_set = 0;
 168                                         break;
 169                                 }
 170                         }
 171                         if ((lowest_max_mas_in_deep > max_mas_in_set) && max_mas_in_set) {
 172                                 lowest_max_mas_in_deep = max_mas_in_set;
 173
 174                                 tmp_csi.start_col = start_col;
 175                         }
 176                         col_start_set += (interval >> deep);
 177                 }
 178
 179                 if (lowest_max_mas_in_deep < 8) {
 180                         csi->start_col = tmp_csi.start_col;
 181                         found = UWB_RSV_ALLOC_FOUND;
 182                         break;
 183                 } else if ((lowest_max_mas_in_deep > 8) &&
 184                            (lowest_max_mas_in_deep != UWB_MAS_PER_ZONE) &&
 185                            (found == UWB_RSV_ALLOC_NOT_FOUND)) {
 186                         csi->start_col = tmp_csi.start_col;
 187                         found = UWB_RSV_ALLOC_FOUND;
 188                 }
 189         }
 190
 191         if (found == UWB_RSV_ALLOC_FOUND) {
 192                 csi->interval = interval;
 193                 csi->safe_mas_per_col = num_safe_mas;
 194                 csi->unsafe_mas_per_col = num_unsafe_mas;
 195
 196                 ai->safe_allocated_mases = (UWB_NUM_ZONES / interval) * num_safe_mas;
 197                 ai->unsafe_allocated_mases = (UWB_NUM_ZONES / interval) * num_unsafe_mas;
 198                 ai->total_allocated_mases = ai->safe_allocated_mases + ai->unsafe_allocated_mases;
 199                 ai->interval = interval;
 200         }
 201         return found;
 202 }
 203
 204 static void get_row_descriptors(struct uwb_rsv_alloc_info *ai)
 205 {
 206         unsigned char *bm = ai->bm;
 207         struct uwb_rsv_row_info *ri = &ai->ri;
 208         int col, mas;
 209
 210         ri->free_rows = 16;
 211         for (mas = 0; mas < UWB_MAS_PER_ZONE; mas ++) {
 212                 ri->avail[mas] = 1;
 213                 for (col = 1; col < UWB_NUM_ZONES; col++) {
 214                         if (bm[col * UWB_NUM_ZONES + mas] == UWB_RSV_MAS_NOT_AVAIL) {
 215                                 ri->free_rows--;
 216                                 ri->avail[mas]=0;
 217                                 break;
 218                         }
 219                 }
 220         }
 221 }
 222
 223 static void uwb_rsv_fill_column_info(unsigned char *bm, int column, struct uwb_rsv_col_info *rci)
 224 {
 225         int mas;
 226         int block_count = 0, start_block = 0;
 227         int previous_avail = 0;
 228         int available = 0;
 229         int safe_mas_in_row[UWB_MAS_PER_ZONE] = {
 230                 8, 7, 6, 5, 4, 4, 4, 4, 4, 4, 4, 4, 4, 3, 2, 1,
 231         };
 232
 233         rci->max_avail_safe = 0;
 234
 235         for (mas = 0; mas < UWB_MAS_PER_ZONE; mas ++) {
 236                 if (!bm[column * UWB_NUM_ZONES + mas]) {
 237                         available++;
 238                         rci->max_avail_unsafe = available;
 239
 240                         rci->highest_mas[available] = mas;
 241
 242                         if (previous_avail) {
 243                                 block_count++;
 244                                 if ((block_count > safe_mas_in_row[start_block]) &&
 245                                     (!rci->max_avail_safe))
 246                                         rci->max_avail_safe = available - 1;
 247                         } else {
 248                                 previous_avail = 1;
 249                                 start_block = mas;
 250                                 block_count = 1;
 251                         }
 252                 } else {
 253                         previous_avail = 0;
 254                 }
 255         }
 256         if (!rci->max_avail_safe)
 257                 rci->max_avail_safe = rci->max_avail_unsafe;
 258 }
 259
 260 static void get_column_descriptors(struct uwb_rsv_alloc_info *ai)
 261 {
 262         unsigned char *bm = ai->bm;
 263         struct uwb_rsv_col_info *ci = ai->ci;
 264         int col;
 265
 266         for (col = 1; col < UWB_NUM_ZONES; col++) {
 267                 uwb_rsv_fill_column_info(bm, col, &ci[col]);
 268         }
 269 }
 270
 271 static int uwb_rsv_find_best_row_alloc(struct uwb_rsv_alloc_info *ai)
 272 {
 273         int n_rows;
 274         int max_rows = ai->max_mas / UWB_USABLE_MAS_PER_ROW;
 275         int min_rows = ai->min_mas / UWB_USABLE_MAS_PER_ROW;
 276         if (ai->min_mas % UWB_USABLE_MAS_PER_ROW)
 277                 min_rows++;
 278         for (n_rows = max_rows; n_rows >= min_rows; n_rows--) {
 279                 if (n_rows <= ai->ri.free_rows) {
 280                         ai->ri.used_rows = n_rows;
 281                         ai->interval = 1; /* row reservation */
 282                         uwb_rsv_fill_row_alloc(ai);
 283                         return UWB_RSV_ALLOC_FOUND;
 284                 }
 285         }
 286         return UWB_RSV_ALLOC_NOT_FOUND;
 287 }
 288
 289 static int uwb_rsv_find_best_col_alloc(struct uwb_rsv_alloc_info *ai, int interval)
 290 {
 291         int n_safe, n_unsafe, n_mas;
 292         int n_column = UWB_NUM_ZONES / interval;
 293         int max_per_zone = ai->max_mas / n_column;
 294         int min_per_zone = ai->min_mas / n_column;
 295
 296         if (ai->min_mas % n_column)
 297                 min_per_zone++;
 298
 299         if (min_per_zone > UWB_MAS_PER_ZONE) {
 300                 return UWB_RSV_ALLOC_NOT_FOUND;
 301         }
 302
 303         if (max_per_zone > UWB_MAS_PER_ZONE) {
 304                 max_per_zone = UWB_MAS_PER_ZONE;
 305         }
 306
 307         for (n_mas = max_per_zone; n_mas >= min_per_zone; n_mas--) {
 308                 if (uwb_rsv_find_best_column_set(ai, interval, 0, n_mas) == UWB_RSV_ALLOC_NOT_FOUND)
 309                         continue;
 310                 for (n_safe = n_mas; n_safe >= 0; n_safe--) {
 311                         n_unsafe = n_mas - n_safe;
 312                         if (uwb_rsv_find_best_column_set(ai, interval, n_safe, n_unsafe) == UWB_RSV_ALLOC_FOUND) {
 313                                 uwb_rsv_fill_column_alloc(ai);
 314                                 return UWB_RSV_ALLOC_FOUND;
 315                         }
 316                 }
 317         }
 318         return UWB_RSV_ALLOC_NOT_FOUND;
 319 }
 320
 321 int uwb_rsv_find_best_allocation(struct uwb_rsv *rsv, struct uwb_mas_bm *available,
 322                                  struct uwb_mas_bm *result)
 323 {
 324         struct uwb_rsv_alloc_info *ai;
 325         int interval;
 326         int bit_index;
 327
 328         ai = kzalloc(sizeof(struct uwb_rsv_alloc_info), GFP_KERNEL);
 329         if (!ai)
 330                 return UWB_RSV_ALLOC_NOT_FOUND;
 331         ai->min_mas = rsv->min_mas;
 332         ai->max_mas = rsv->max_mas;
 333         ai->max_interval = rsv->max_interval;
 334
 335
 336         /* fill the not available vector from the available bm */
 337         for (bit_index = 0; bit_index < UWB_NUM_MAS; bit_index++) {
 338                 if (!test_bit(bit_index, available->bm))
 339                         ai->bm[bit_index] = UWB_RSV_MAS_NOT_AVAIL;
 340         }
 341
 342         if (ai->max_interval == 1) {
 343                 get_row_descriptors(ai);
 344                 if (uwb_rsv_find_best_row_alloc(ai) == UWB_RSV_ALLOC_FOUND)
 345                         goto alloc_found;
 346                 else
 347                         goto alloc_not_found;
 348         }
 349
 350         get_column_descriptors(ai);
 351
 352         for (interval = 16; interval >= 2; interval>>=1) {
 353                 if (interval > ai->max_interval)
 354                         continue;
 355                 if (uwb_rsv_find_best_col_alloc(ai, interval) == UWB_RSV_ALLOC_FOUND)
 356                         goto alloc_found;
 357         }
 358
 359         /* try row reservation if no column is found */
 360         get_row_descriptors(ai);
 361         if (uwb_rsv_find_best_row_alloc(ai) == UWB_RSV_ALLOC_FOUND)
 362                 goto alloc_found;
 363         else
 364                 goto alloc_not_found;
 365
 366   alloc_found:
 367         bitmap_zero(result->bm, UWB_NUM_MAS);
 368         bitmap_zero(result->unsafe_bm, UWB_NUM_MAS);
 369         /* fill the safe and unsafe bitmaps */
 370         for (bit_index = 0; bit_index < UWB_NUM_MAS; bit_index++) {
 371                 if (ai->bm[bit_index] == UWB_RSV_MAS_SAFE)
 372                         set_bit(bit_index, result->bm);
 373                 else if (ai->bm[bit_index] == UWB_RSV_MAS_UNSAFE)
 374                         set_bit(bit_index, result->unsafe_bm);
 375         }
 376         bitmap_or(result->bm, result->bm, result->unsafe_bm, UWB_NUM_MAS);
 377
 378         result->safe   = ai->safe_allocated_mases;
 379         result->unsafe = ai->unsafe_allocated_mases;
 380
 381         kfree(ai);
 382         return UWB_RSV_ALLOC_FOUND;
 383
 384   alloc_not_found:
 385         kfree(ai);
 386         return UWB_RSV_ALLOC_NOT_FOUND;
 387 }