src/afb-perm.c

   1 /*
   2  * Copyright (C) 2017 "IoT.bzh"
   3  * Author José Bollo <jose.bollo@iot.bzh>
   4  *
   5  * Licensed under the Apache License, Version 2.0 (the "License");
   6  * you may not use this file except in compliance with the License.
   7  * You may obtain a copy of the License at
   8  *
   9  *   http://www.apache.org/licenses/LICENSE-2.0
  10  *
  11  * Unless required by applicable law or agreed to in writing, software
  12  * distributed under the License is distributed on an "AS IS" BASIS,
  13  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  14  * See the License for the specific language governing permissions and
  15  * limitations under the License.
  16  */
  17
  18
  19 #include <stdlib.h>
  20 #include <assert.h>
  21 #include <string.h>
  22 #include <errno.h>
  23 #include <ctype.h>
  24
  25 #include "afb-perm.h"
  26 #include "verbose.h"
  27
  28 /*********************************************************************
  29 *** SECTION node
  30 *********************************************************************/
  31
  32 /**
  33  * types of nodes
  34  */
  35 enum type
  36 {
  37         Text,   /**< text node */
  38         And,    /**< and node */
  39         Or,     /**< or node */
  40         Not     /**< not node */
  41 };
  42
  43 /**
  44  * structure for nodes
  45  */
  46 struct node
  47 {
  48         enum type type; /**< type of the node */
  49         union {
  50                 struct node *children[2]; /**< possible subnodes */
  51                 char text[1]; /**< text of the node */
  52         };
  53 };
  54
  55 /**
  56  * make a text node and return it
  57  * @param type type of the node (should be Text)
  58  * @param text the text to set for the node
  59  * @param length the length of the text
  60  * @return the allocated node or NULL on memory depletion
  61  */
  62 static struct node *node_make_text(enum type type, const char *text, size_t length)
  63 {
  64         struct node *node;
  65
  66         node = malloc(length + sizeof *node);
  67         if (!node)
  68                 errno = ENOMEM;
  69         else {
  70                 node->type = type;
  71                 memcpy(node->text, text, length);
  72                 node->text[length] = 0;
  73         }
  74         return node;
  75 }
  76
  77 /**
  78  * make a node with sub nodes and return it
  79  * @param type type of the node (should be And, Or or Text)
  80  * @param left the "left" sub node
  81  * @param right the "right" sub node (if any or NULL)
  82  * @return the allocated node or NULL on memory depletion
  83  */
  84 static struct node *node_make_parent(enum type type, struct node *left, struct node *right)
  85 {
  86         struct node *node;
  87
  88         node = malloc(sizeof *node);
  89         if (!node)
  90                 errno = ENOMEM;
  91         else {
  92                 node->type = type;
  93                 node->children[0] = left;
  94                 node->children[1] = right;
  95         }
  96         return node;
  97 }
  98
  99 /**
 100  * Frees the node and its possible subnodes
 101  * @param node the node to free
 102  */
 103 static void node_free(struct node *node)
 104 {
 105         struct node *left, *right;
 106
 107         if (node) {
 108                 switch (node->type) {
 109                 case Text:
 110                         free(node);
 111                         break;
 112                 case And:
 113                 case Or:
 114                         left = node->children[0];
 115                         right = node->children[1];
 116                         free(node);
 117                         node_free(left);
 118                         node_free(right);
 119                         break;
 120                 case Not:
 121                         left = node->children[0];
 122                         free(node);
 123                         node_free(left);
 124                         break;
 125                 }
 126         }
 127 }
 128
 129 /**
 130  * Checks the permissions for the 'node' using the 'check' function
 131  * and its 'closure'.
 132  * @param node the node to check
 133  * @param check the function that checks if a pernmission of 'name' is granted for 'closure'
 134  * @param closure the context closure for the function 'check'
 135  * @return 1 if the permission is granted or 0 otherwise
 136  */
 137 static int node_check(struct node *node, int (*check)(void *closure, const char *name), void *closure)
 138 {
 139         for(;;) {
 140                 switch (node->type) {
 141                 case Text:
 142                         return check(closure, node->text);
 143                 case And:
 144                         if (!node_check(node->children[0], check, closure))
 145                                 return 0;
 146                         break;
 147                 case Or:
 148                         if (node_check(node->children[0], check, closure))
 149                                 return 1;
 150                         break;
 151                 case Not:
 152                         return !node_check(node->children[0], check, closure);
 153                 }
 154                 node = node->children[1];
 155         }
 156 }
 157
 158 /*********************************************************************
 159 *** SECTION parse
 160 *********************************************************************/
 161
 162 /**
 163  * the symbol types
 164  */
 165 enum symbol
 166 {
 167         TEXT,   /**< a common text, name of a permission */
 168         AND,    /**< and keyword */
 169         OR,     /**< or keyword */
 170         NOT,    /**< not keyword */
 171         OBRA,   /**< open bracket */
 172         CBRA,   /**< close bracket */
 173         END     /**< end of input */
 174 };
 175
 176 /**
 177  * structure for parsing permission description
 178  */
 179 struct parse
 180 {
 181         const char *desc;       /**< initial permission description */
 182         const char *symbol;     /**< current symbol parsed */
 183         size_t symlen;          /**< length of the current symbol */
 184         enum symbol type;       /**< type of the current symbol */
 185 };
 186
 187 /**
 188  * updates parse to point to the next symbol if any
 189  * @param parse parser state to update
 190  */
 191 static void parse_next(struct parse *parse)
 192 {
 193         const char *scan;
 194         size_t len;
 195
 196         /* skip current symbol */
 197         scan = &parse->symbol[parse->symlen];
 198
 199         /* skip white spaces */
 200         while (*scan && isspace(*scan))
 201                 scan++;
 202
 203         /* scan the symbol */
 204         switch (*scan) {
 205         case 0:
 206                 len = 0;
 207                 parse->type = END;
 208                 break;
 209         case '(':
 210                 len = 1;
 211                 parse->type = OBRA;
 212                 break;
 213         case ')':
 214                 len = 1;
 215                 parse->type = CBRA;
 216                 break;
 217         default:
 218                 /* compute the length */
 219                 len = 0;
 220                 while (scan[len] && !isspace(scan[len]) && scan[len] != ')' && scan[len] != '(')
 221                         len++;
 222                 parse->type = TEXT;
 223
 224                 /* fall to keyword if any */
 225                 switch(len) {
 226                 case 2:
 227                         if (!strncasecmp(scan, "or", len))
 228                                 parse->type = OR;
 229                         break;
 230                 case 3:
 231                         if (!strncasecmp(scan, "and", len))
 232                                 parse->type = AND;
 233                         else if (!strncasecmp(scan, "not", len))
 234                                 parse->type = NOT;
 235                         break;
 236                 }
 237                 break;
 238         }
 239         parse->symbol = scan;
 240         parse->symlen = len;
 241 }
 242
 243 /**
 244  * Init the parser state 'parse' for the description 'desc'
 245  * @param parse the parser state to initialise
 246  * @param desc the description of the permissions to be parsed
 247  */
 248 static void parse_init(struct parse *parse, const char *desc)
 249 {
 250         parse->desc = desc;
 251         parse->symbol = desc;
 252         parse->symlen = 0;
 253         parse_next(parse);
 254 }
 255
 256 /*********************************************************************
 257 *** SECTION node_parse
 258 *********************************************************************/
 259
 260 static struct node *node_parse_or(struct parse *parse);
 261
 262 /**
 263  * Parse a permission name
 264  * @param parser the parser state
 265  * @return the parsed node or NULL in case of error
 266  * in case of error errno is set to EINVAL or ENOMEM
 267  */
 268 static struct node *node_parse_text(struct parse *parse)
 269 {
 270         struct node *node;
 271
 272         if (parse->type == TEXT) {
 273                 node = node_make_text(Text, parse->symbol, parse->symlen);
 274                 parse_next(parse);
 275         } else {
 276                 errno = EINVAL;
 277                 node = NULL;
 278         }
 279         return node;
 280 }
 281
 282 /**
 283  * Parse a term that is either a name (text) or a sub expression
 284  * enclosed in brackets.
 285  * @param parser the parser state
 286  * @return the parsed node or NULL in case of error
 287  * in case of error errno is set to EINVAL or ENOMEM
 288  */
 289 static struct node *node_parse_term(struct parse *parse)
 290 {
 291         struct node *node;
 292
 293         if (parse->type != OBRA)
 294                 node = node_parse_text(parse);
 295         else {
 296                 parse_next(parse);
 297                 node = node_parse_or(parse);
 298                 if (parse->type == CBRA)
 299                         parse_next(parse);
 300                 else {
 301                         errno = EINVAL;
 302                         node_free(node);
 303                         node = NULL;
 304                 }
 305         }
 306         return node;
 307 }
 308
 309 /**
 310  * Parse a term potentially prefixed by not.
 311  * @param parser the parser state
 312  * @return the parsed node or NULL in case of error
 313  * in case of error errno is set to EINVAL or ENOMEM
 314  */
 315 static struct node *node_parse_not(struct parse *parse)
 316 {
 317         struct node *node, *not;
 318
 319         if (parse->type != NOT)
 320                 node = node_parse_term(parse);
 321         else {
 322                 parse_next(parse);
 323                 node = node_parse_term(parse);
 324                 if (node) {
 325                         not = node_make_parent(Not, node, NULL);
 326                         if (not)
 327                                 node = not;
 328                         else {
 329                                 node_free(node);
 330                                 node = NULL;
 331                         }
 332                 }
 333         }
 334         return node;
 335 }
 336
 337 /**
 338  * Parse a potential sequence of terms connected with the
 339  * given operator (AND or OR). The function takes care to
 340  * create an evaluation tree that respects the order given
 341  * by the description and that will limit the recursivity
 342  * depth.
 343  * @param parser the parser state
 344  * @param operator the symbol type of the operator scanned
 345  * @param subparse the function for parsing terms of the sequence
 346  * @param type the node type corresponding to the operator
 347  * @return the parsed node or NULL in case of error
 348  * in case of error errno is set to EINVAL or ENOMEM
 349  */
 350 static struct node *node_parse_infix(
 351                 struct parse *parse,
 352                 enum symbol operator,
 353                 struct node *(*subparse)(struct parse*),
 354                 enum type type
 355 )
 356 {
 357         struct node *root, **up, *right, *node;
 358
 359         root = subparse(parse);
 360         if (root) {
 361                 up = &root;
 362                 while (parse->type == operator) {
 363                         parse_next(parse);
 364                         right = subparse(parse);
 365                         if (!right) {
 366                                 node_free(root);
 367                                 root = NULL;
 368                                 break;
 369                         }
 370                         node = node_make_parent(type, *up, right);
 371                         if (!node) {
 372                                 node_free(right);
 373                                 node_free(root);
 374                                 root = NULL;
 375                                 break;
 376                         }
 377                         *up = node;
 378                         up = &node->children[1];
 379                 }
 380         }
 381         return root;
 382 }
 383
 384 /**
 385  * Parse a potential sequence of anded terms.
 386  * @param parser the parser state
 387  * @return the parsed node or NULL in case of error
 388  * in case of error errno is set to EINVAL or ENOMEM
 389  */
 390 static struct node *node_parse_and(struct parse *parse)
 391 {
 392         return node_parse_infix(parse, AND, node_parse_not, And);
 393 }
 394
 395 /**
 396  * Parse a potential sequence of ored terms.
 397  * @param parser the parser state
 398  * @return the parsed node or NULL in case of error
 399  * in case of error errno is set to EINVAL or ENOMEM
 400  */
 401 static struct node *node_parse_or(struct parse *parse)
 402 {
 403         return node_parse_infix(parse, OR, node_parse_and, Or);
 404 }
 405
 406 /**
 407  * Parse description of permissions.
 408  * @param desc the description to parse
 409  * @return the parsed node or NULL in case of error
 410  * in case of error errno is set to EINVAL or ENOMEM
 411  */
 412 static struct node *node_parse(const char *desc)
 413 {
 414         struct node *node;
 415         struct parse parse;
 416
 417         parse_init(&parse, desc);
 418         node = node_parse_or(&parse);
 419         if (node && parse.type != END) {
 420                 node_free(node);
 421                 node = NULL;
 422         }
 423         return node;
 424 }
 425
 426 /*********************************************************************
 427 *** SECTION perm
 428 *********************************************************************/
 429
 430 /**
 431  * structure for storing permissions
 432  */
 433 struct afb_perm
 434 {
 435         struct node *root;      /**< root node descripbing the permission */
 436         int refcount;           /**< the count of use of the structure */
 437 };
 438
 439 /**
 440  * allocates the structure for the given root
 441  * @param root the root node to keep
 442  * @return the created permission object or NULL
 443  */
 444 static struct afb_perm *make_perm(struct node *root)
 445 {
 446         struct afb_perm *perm;
 447
 448         perm = malloc(sizeof *perm);
 449         if (!perm)
 450                 errno = ENOMEM;
 451         else {
 452                 perm->root = root;
 453                 perm->refcount = 1;
 454         }
 455         return perm;
 456 }
 457
 458 /**
 459  * Creates the permission for the given description
 460  * @param desc the description of the permission to create
 461  * @return the created permission object or NULL
 462  */
 463 struct afb_perm *afb_perm_parse(const char *desc)
 464 {
 465         struct node *root;
 466         struct afb_perm *perm;
 467
 468         root = node_parse(desc);
 469         if (root) {
 470                 perm = make_perm(root);
 471                 if (perm)
 472                         return perm;
 473                 node_free(root);
 474         }
 475         return NULL;
 476 }
 477
 478 /**
 479  * Adds a reference to the permissions
 480  * @param perm the permission to reference
 481  */
 482 void afb_perm_addref(struct afb_perm *perm)
 483 {
 484         assert(perm);
 485         perm->refcount++;
 486 }
 487
 488 /**
 489  * Removes a reference to the permissions
 490  * @param perm the permission to dereference
 491  */
 492 void afb_perm_unref(struct afb_perm *perm)
 493 {
 494         if (perm && !--perm->refcount) {
 495                 node_free(perm->root);
 496                 free(perm);
 497         }
 498 }
 499
 500 /**
 501  * Checks permission 'perm' using the 'check' function
 502  * and its 'closure'.
 503  * @param perm the permission to check
 504  * @param check the function that checks if a pernmission of 'name' is granted for 'closure'
 505  * @param closure the context closure for the function 'check'
 506  * @return 1 if the permission is granted or 0 otherwise
 507  */
 508 int afb_perm_check(struct afb_perm *perm, int (*check)(void *closure, const char *name), void *closure)
 509 {
 510         return node_check(perm->root, check, closure);
 511 }
 512
 513