lib/admin_group.c

   1 /*
   2  * Administrative-group library (RFC3630, RFC5305, RFC5329, RFC7308)
   3  *
   4  * Copyright 2022 Hiroki Shirokura, LINE Corporation
   5  * Copyright 2022 Masakazu Asama
   6  * Copyright 2022 6WIND S.A.
   7  *
   8  * This program is free software; you can redistribute it and/or modify it
   9  * under the terms of the GNU General Public License as published by the Free
  10  * Software Foundation; either version 2 of the License, or (at your option)
  11  * any later version.
  12  *
  13  * This program is distributed in the hope that it will be useful, but WITHOUT
  14  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  15  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License for
  16  * more details.
  17  *
  18  * You should have received a copy of the GNU General Public License along
  19  * with this program; see the file COPYING; if not, write to the Free Software
  20  * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
  21  */
  22
  23 #include "admin_group.h"
  24 #include "bitfield.h"
  25
  26 char *admin_group_string(char *out, size_t sz, int indent,
  27                          const struct admin_group *ag)
  28 {
  29         bool printed = false;
  30         size_t index = 2;
  31         int nb_print = 0;
  32
  33         if (sz < index)
  34                 return out;
  35
  36         if (admin_group_explicit_zero(ag)) {
  37                 snprintf(out, sz, "0x00000000");
  38                 return out;
  39         }
  40
  41         if (admin_group_zero(ag)) {
  42                 snprintf(out, sz, "not-set");
  43                 return out;
  44         }
  45
  46         snprintf(out, sz, "0x");
  47         for (ssize_t i = ag->bitmap.m - 1; i >= 0; i--) {
  48                 if (sz - index <= 0)
  49                         break;
  50                 if (ag->bitmap.data[i] == 0 && !printed)
  51                         continue;
  52                 if (nb_print != 0 && (nb_print % 4) == 0) {
  53                         snprintf(&out[index], sz - index, "\n%*s", indent, "");
  54                         index += indent + 1;
  55                         snprintf(&out[index], sz - index, "0x%08x ",
  56                                  ag->bitmap.data[i]);
  57                         index += 2;
  58                 } else
  59                         snprintf(&out[index], sz - index, "%08x ",
  60                                  ag->bitmap.data[i]);
  61                 index += 9;
  62                 nb_print++;
  63                 printed = true;
  64         }
  65         return out;
  66 }
  67
  68 char *admin_group_standard_print(char *out, int indent, uint32_t bitmap)
  69 {
  70         bool first = true;
  71         int bit, i;
  72         size_t ret, line_sz = 0, line_max_sz;
  73
  74         out[0] = '\0';
  75
  76         if (bitmap == 0) {
  77                 snprintf(out, ADMIN_GROUP_PRINT_MAX_SIZE, "not-set");
  78                 return out;
  79         }
  80
  81         line_max_sz = strlen("0xffffffff ffffffff ffffffff ffffffff");
  82
  83         for (i = 0; i < 32; i++) {
  84                 bit = bitmap >> i & 1;
  85                 if (bit == 0)
  86                         continue;
  87                 if (!first) {
  88                         ret = snprintf(&out[strlen(out)],
  89                                        ADMIN_GROUP_PRINT_MAX_SIZE - strlen(out),
  90                                        ", ");
  91                         line_sz += ret;
  92                 }
  93                 if (line_sz >= line_max_sz) {
  94                         snprintf(&out[strlen(out)],
  95                                  ADMIN_GROUP_PRINT_MAX_SIZE - strlen(out),
  96                                  "\n%*s", indent, "");
  97
  98                         line_sz = 0;
  99                 }
 100                 ret = snprintf(&out[strlen(out)],
 101                                ADMIN_GROUP_PRINT_MAX_SIZE - strlen(out), "%d",
 102                                i);
 103                 line_sz += ret;
 104                 first = false;
 105         }
 106
 107         return out;
 108 }
 109
 110 char *admin_group_print(char *out, int indent, const struct admin_group *ag)
 111 {
 112         bool first = true;
 113         uint32_t i;
 114         size_t ret, line_sz = 0, line_max_sz;
 115
 116         out[0] = '\0';
 117
 118         if (admin_group_size(ag) == 0) {
 119                 snprintf(out, ADMIN_GROUP_PRINT_MAX_SIZE, "not-set");
 120                 return out;
 121         }
 122
 123         line_max_sz = strlen("0xffffffff ffffffff ffffffff ffffffff");
 124
 125         for (i = 0; i < (admin_group_size(ag) * WORD_SIZE); i++) {
 126                 if (!admin_group_get(ag, i))
 127                         continue;
 128                 if (!first) {
 129                         ret = snprintf(&out[strlen(out)],
 130                                        ADMIN_GROUP_PRINT_MAX_SIZE - strlen(out),
 131                                        ", ");
 132                         line_sz += ret;
 133                 }
 134                 if (line_sz >= line_max_sz) {
 135                         snprintf(&out[strlen(out)],
 136                                  ADMIN_GROUP_PRINT_MAX_SIZE - strlen(out),
 137                                  "\n%*s", indent, "");
 138
 139                         line_sz = 0;
 140                 }
 141                 ret = snprintf(&out[strlen(out)],
 142                                ADMIN_GROUP_PRINT_MAX_SIZE - strlen(out), "%d",
 143                                i);
 144                 line_sz += ret;
 145                 if (ret >= (ADMIN_GROUP_PRINT_MAX_SIZE - strlen(out))) {
 146                         out[0] = '\0';
 147                         return out;
 148                 }
 149                 first = false;
 150         }
 151
 152         return out;
 153 }
 154
 155 bool admin_group_cmp(const struct admin_group *ag1,
 156                      const struct admin_group *ag2)
 157 {
 158         size_t i;
 159
 160         for (i = 0; i < ag1->bitmap.m || i < ag2->bitmap.m; i++) {
 161                 if (i >= ag1->bitmap.m) {
 162                         if (ag2->bitmap.data[i] != 0)
 163                                 return false;
 164                 } else if (i >= ag2->bitmap.m) {
 165                         if (ag1->bitmap.data[i] != 0)
 166                                 return false;
 167                 } else if (memcmp(&ag1->bitmap.data[i], &ag2->bitmap.data[i],
 168                                   sizeof(word_t)) != 0)
 169                         return false;
 170         }
 171
 172         return true;
 173 }
 174
 175 void admin_group_copy(struct admin_group *dst, const struct admin_group *src)
 176 {
 177         assert(bf_is_inited(src->bitmap));
 178         if (bf_is_inited(dst->bitmap))
 179                 bf_free(dst->bitmap);
 180         dst->bitmap = bf_copy(src->bitmap);
 181 }
 182
 183 void admin_group_init(struct admin_group *ag)
 184 {
 185         assert(!bf_is_inited(ag->bitmap));
 186         bf_init(ag->bitmap, WORD_SIZE);
 187 }
 188
 189 void admin_group_term(struct admin_group *ag)
 190 {
 191         assert(bf_is_inited(ag->bitmap));
 192         bf_free(ag->bitmap);
 193 }
 194
 195 word_t admin_group_get_offset(const struct admin_group *ag, size_t oct_offset)
 196 {
 197         assert(bf_is_inited(ag->bitmap));
 198         if (ag->bitmap.m < oct_offset)
 199                 return 0;
 200         return ag->bitmap.data[oct_offset];
 201 }
 202
 203 static void admin_group_extend(struct admin_group *ag, size_t idx)
 204 {
 205         size_t old_m, m;
 206
 207         old_m = ag->bitmap.m;
 208         m = idx + 1;
 209         ag->bitmap.m = m;
 210         ag->bitmap.data =
 211                 XREALLOC(MTYPE_BITFIELD, ag->bitmap.data, m * sizeof(word_t));
 212         memset(&ag->bitmap.data[old_m], 0, (m - old_m) * sizeof(word_t));
 213 }
 214
 215 void admin_group_set(struct admin_group *ag, size_t pos)
 216 {
 217         size_t idx = bf_index(pos);
 218
 219         if (idx >= ag->bitmap.m)
 220                 admin_group_extend(ag, idx);
 221
 222         ag->bitmap.data[idx] |= 1 << (bf_offset(pos));
 223
 224         if (idx >= ag->bitmap.n)
 225                 ag->bitmap.n = idx + 1;
 226 }
 227
 228 void admin_group_unset(struct admin_group *ag, size_t pos)
 229 {
 230         if (bf_index(pos) > (ag->bitmap.m - 1))
 231                 return;
 232         bf_release_index(ag->bitmap, pos);
 233         ag->bitmap.n = admin_group_size(ag);
 234 }
 235
 236 int admin_group_get(const struct admin_group *ag, size_t pos)
 237 {
 238         size_t admin_group_length = admin_group_size(ag);
 239         uint32_t oct_offset;
 240         size_t idx;
 241
 242         if (admin_group_length == 0)
 243                 return 0;
 244
 245         idx = bf_index(pos);
 246
 247         if (idx >= admin_group_length)
 248                 return 0;
 249
 250         oct_offset = admin_group_get_offset(ag, idx);
 251         return oct_offset >> pos & 1;
 252 }
 253
 254 void admin_group_bulk_set(struct admin_group *ag, uint32_t bitmap,
 255                           size_t oct_offset)
 256 {
 257
 258         if (bitmap == 0 && oct_offset == 0) {
 259                 admin_group_allow_explicit_zero(ag);
 260                 return;
 261         }
 262
 263         if (oct_offset >= ag->bitmap.m)
 264                 admin_group_extend(ag, oct_offset);
 265
 266         ag->bitmap.data[oct_offset] = bitmap;
 267
 268         if (oct_offset >= ag->bitmap.n)
 269                 ag->bitmap.n = oct_offset + 1;
 270 }
 271
 272 size_t admin_group_size(const struct admin_group *ag)
 273 {
 274         size_t size = 0;
 275
 276         for (size_t i = 0; i < ag->bitmap.m; i++)
 277                 if (ag->bitmap.data[i] != 0)
 278                         size = i + 1;
 279         return size;
 280 }
 281
 282 size_t admin_group_nb_words(const struct admin_group *ag)
 283 {
 284         return ag->bitmap.n;
 285 }
 286
 287 void admin_group_clear(struct admin_group *ag)
 288 {
 289         for (size_t i = 0; i < ag->bitmap.m; i++)
 290                 ag->bitmap.data[i] = 0;
 291         ag->bitmap.n = 0;
 292 }
 293
 294 bool admin_group_zero(const struct admin_group *ag)
 295 {
 296         for (size_t i = 0; i < ag->bitmap.m; i++)
 297                 if (ag->bitmap.data[i] != 0)
 298                         return false;
 299         return true;
 300 }
 301
 302
 303 bool admin_group_explicit_zero(const struct admin_group *ag)
 304 {
 305         return ag->bitmap.n == 1 && ag->bitmap.data[0] == 0;
 306 }
 307
 308 void admin_group_allow_explicit_zero(struct admin_group *ag)
 309 {
 310         if (admin_group_zero(ag))
 311                 ag->bitmap.n = 1;
 312 }
 313
 314 void admin_group_disallow_explicit_zero(struct admin_group *ag)
 315 {
 316         if (admin_group_zero(ag))
 317                 ag->bitmap.n = 0;
 318 }
 319
 320 /* link_std_ag: admin-group in the RFC5305 section 3.1 format
 321  * link_ext_ag: admin-group in the RFC7308 format
 322  * RFC7308 specifies in section 2.3.1 that:
 323  * "If both an AG and EAG are present, a receiving node MUST use the AG
 324  * as the first 32 bits (0-31) of administrative color and use the EAG
 325  * for bits 32 and higher, if present."
 326  */
 327 bool admin_group_match_any(const struct admin_group *fad_ag,
 328                            const uint32_t *link_std_ag,
 329                            const struct admin_group *link_ext_ag)
 330 {
 331         size_t fad_ag_sz, link_ag_sz, i;
 332         uint32_t link_ag_bitmap, fad_ag_bitmap;
 333
 334         assert(fad_ag);
 335
 336         /* get the size of admin-groups: i.e. number of used words */
 337         fad_ag_sz = admin_group_size(fad_ag);
 338         if (link_std_ag && link_ext_ag) {
 339                 link_ag_sz = admin_group_size(link_ext_ag);
 340                 if (link_ag_sz == 0)
 341                         link_ag_sz = 1;
 342         } else if (link_std_ag && !link_ext_ag)
 343                 link_ag_sz = 1;
 344         else if (!link_std_ag && link_ext_ag)
 345                 link_ag_sz = admin_group_size(link_ext_ag);
 346         else
 347                 link_ag_sz = 0;
 348
 349         for (i = 0; i < fad_ag_sz && i < link_ag_sz; i++) {
 350                 fad_ag_bitmap = fad_ag->bitmap.data[i];
 351                 if (i == 0 && link_std_ag)
 352                         link_ag_bitmap = *link_std_ag;
 353                 else
 354                         link_ag_bitmap = link_ext_ag->bitmap.data[i];
 355
 356                 if (fad_ag_bitmap & link_ag_bitmap)
 357                         return true;
 358         }
 359         return false;
 360 }
 361
 362 /* same comments as admin_group_match_any() */
 363 bool admin_group_match_all(const struct admin_group *fad_ag,
 364                            const uint32_t *link_std_ag,
 365                            const struct admin_group *link_ext_ag)
 366 {
 367         size_t fad_ag_sz, link_ag_sz, i;
 368         uint32_t link_ag_bitmap, fad_ag_bitmap;
 369
 370         assert(fad_ag);
 371
 372         /* get the size of admin-groups: i.e. number of used words */
 373         fad_ag_sz = admin_group_size(fad_ag);
 374         if (link_std_ag && link_ext_ag) {
 375                 link_ag_sz = admin_group_size(link_ext_ag);
 376                 if (link_ag_sz == 0)
 377                         link_ag_sz = 1;
 378         } else if (link_std_ag && !link_ext_ag)
 379                 link_ag_sz = 1;
 380         else if (!link_std_ag && link_ext_ag)
 381                 link_ag_sz = admin_group_size(link_ext_ag);
 382         else
 383                 link_ag_sz = 0;
 384
 385         if (fad_ag_sz > link_ag_sz)
 386                 return false;
 387
 388         for (i = 0; i < fad_ag_sz; i++) {
 389                 fad_ag_bitmap = fad_ag->bitmap.data[i];
 390                 if (fad_ag_bitmap == 0)
 391                         continue;
 392
 393                 if (i == 0 && link_std_ag)
 394                         link_ag_bitmap = *link_std_ag;
 395                 else
 396                         link_ag_bitmap = link_ext_ag->bitmap.data[i];
 397
 398                 if ((fad_ag_bitmap & link_ag_bitmap) != fad_ag_bitmap)
 399                         return false;
 400         }
 401         return true;
 402 }