contrib/ldns/dname.c

   1 /*
   2  * dname.c
   3  *
   4  * dname specific rdata implementations
   5  * A dname is a rdf structure with type LDNS_RDF_TYPE_DNAME
   6  * It is not a /real/ type! All function must therefore check
   7  * for LDNS_RDF_TYPE_DNAME.
   8  *
   9  * a Net::DNS like library for C
  10  *
  11  * (c) NLnet Labs, 2004-2006
  12  *
  13  * See the file LICENSE for the license
  14  */
  15
  16 #include <ldns/config.h>
  17
  18 #include <ldns/ldns.h>
  19
  20 #ifdef HAVE_NETINET_IN_H
  21 #include <netinet/in.h>
  22 #endif
  23 #ifdef HAVE_SYS_SOCKET_H
  24 #include <sys/socket.h>
  25 #endif
  26 #ifdef HAVE_NETDB_H
  27 #include <netdb.h>
  28 #endif
  29 #ifdef HAVE_ARPA_INET_H
  30 #include <arpa/inet.h>
  31 #endif
  32
  33 /* Returns whether the last label in the name is a root label (a empty label).
  34  * Note that it is not enough to just test the last character to be 0,
  35  * because it may be part of the last label itself.
  36  */
  37 static bool
  38 ldns_dname_last_label_is_root_label(const ldns_rdf* dname)
  39 {
  40         size_t src_pos;
  41         size_t len = 0;
  42
  43         for (src_pos = 0; src_pos < ldns_rdf_size(dname); src_pos += len + 1) {
  44                 len = ldns_rdf_data(dname)[src_pos];
  45         }
  46         assert(src_pos == ldns_rdf_size(dname));
  47
  48         return src_pos > 0 && len == 0;
  49 }
  50
  51 ldns_rdf *
  52 ldns_dname_cat_clone(const ldns_rdf *rd1, const ldns_rdf *rd2)
  53 {
  54         ldns_rdf *new;
  55         uint16_t new_size;
  56         uint8_t *buf;
  57         uint16_t left_size;
  58
  59         if (ldns_rdf_get_type(rd1) != LDNS_RDF_TYPE_DNAME ||
  60                         ldns_rdf_get_type(rd2) != LDNS_RDF_TYPE_DNAME) {
  61                 return NULL;
  62         }
  63
  64         /* remove root label if it is present at the end of the left
  65          * rd, by reducing the size with 1
  66          */
  67         left_size = ldns_rdf_size(rd1);
  68         if (ldns_dname_last_label_is_root_label(rd1)) {
  69                 left_size--;
  70         }
  71
  72         /* we overwrite the nullbyte of rd1 */
  73         new_size = left_size + ldns_rdf_size(rd2);
  74         buf = LDNS_XMALLOC(uint8_t, new_size);
  75         if (!buf) {
  76                 return NULL;
  77         }
  78
  79         /* put the two dname's after each other */
  80         memcpy(buf, ldns_rdf_data(rd1), left_size);
  81         memcpy(buf + left_size, ldns_rdf_data(rd2), ldns_rdf_size(rd2));
  82
  83         new = ldns_rdf_new_frm_data(LDNS_RDF_TYPE_DNAME, new_size, buf);
  84
  85         LDNS_FREE(buf);
  86         return new;
  87 }
  88
  89 ldns_status
  90 ldns_dname_cat(ldns_rdf *rd1, const ldns_rdf *rd2)
  91 {
  92         uint16_t left_size;
  93         uint16_t size;
  94         uint8_t* newd;
  95
  96         if (ldns_rdf_get_type(rd1) != LDNS_RDF_TYPE_DNAME ||
  97                         ldns_rdf_get_type(rd2) != LDNS_RDF_TYPE_DNAME) {
  98                 return LDNS_STATUS_ERR;
  99         }
 100
 101         /* remove root label if it is present at the end of the left
 102          * rd, by reducing the size with 1
 103          */
 104         left_size = ldns_rdf_size(rd1);
 105         if (ldns_dname_last_label_is_root_label(rd1)) {
 106                 left_size--;
 107         }
 108
 109         size = left_size + ldns_rdf_size(rd2);
 110         newd = LDNS_XREALLOC(ldns_rdf_data(rd1), uint8_t, size);
 111         if(!newd) {
 112                 return LDNS_STATUS_MEM_ERR;
 113         }
 114
 115         ldns_rdf_set_data(rd1, newd);
 116         memcpy(ldns_rdf_data(rd1) + left_size, ldns_rdf_data(rd2),
 117                         ldns_rdf_size(rd2));
 118         ldns_rdf_set_size(rd1, size);
 119
 120         return LDNS_STATUS_OK;
 121 }
 122
 123 ldns_rdf*
 124 ldns_dname_reverse(const ldns_rdf *dname)
 125 {
 126         size_t rd_size;
 127         uint8_t* buf;
 128         ldns_rdf* new;
 129         size_t src_pos;
 130         size_t len ;
 131
 132         assert(ldns_rdf_get_type(dname) == LDNS_RDF_TYPE_DNAME);
 133
 134         rd_size = ldns_rdf_size(dname);
 135         buf = LDNS_XMALLOC(uint8_t, rd_size);
 136         if (! buf) {
 137                 return NULL;
 138         }
 139         new = ldns_rdf_new(LDNS_RDF_TYPE_DNAME, rd_size, buf);
 140         if (! new) {
 141                 LDNS_FREE(buf);
 142                 return NULL;
 143         }
 144
 145         /* If dname ends in a root label, the reverse should too.
 146          */
 147         if (ldns_dname_last_label_is_root_label(dname)) {
 148                 buf[rd_size - 1] = 0;
 149                 rd_size -= 1;
 150         }
 151         for (src_pos = 0; src_pos < rd_size; src_pos += len + 1) {
 152                 len = ldns_rdf_data(dname)[src_pos];
 153                 memcpy(&buf[rd_size - src_pos - len - 1],
 154                                 &ldns_rdf_data(dname)[src_pos], len + 1);
 155         }
 156         return new;
 157 }
 158
 159 ldns_rdf *
 160 ldns_dname_clone_from(const ldns_rdf *d, uint16_t n)
 161 {
 162         uint8_t *data;
 163         uint8_t label_size;
 164         size_t data_size;
 165
 166         if (!d ||
 167             ldns_rdf_get_type(d) != LDNS_RDF_TYPE_DNAME ||
 168             ldns_dname_label_count(d) < n) {
 169                 return NULL;
 170         }
 171
 172         data = ldns_rdf_data(d);
 173         data_size = ldns_rdf_size(d);
 174         while (n > 0) {
 175                 label_size = data[0] + 1;
 176                 data += label_size;
 177                 if (data_size < label_size) {
 178                         /* this label is very broken */
 179                         return NULL;
 180                 }
 181                 data_size -= label_size;
 182                 n--;
 183         }
 184
 185         return ldns_dname_new_frm_data(data_size, data);
 186 }
 187
 188 ldns_rdf *
 189 ldns_dname_left_chop(const ldns_rdf *d)
 190 {
 191         uint8_t label_pos;
 192         ldns_rdf *chop;
 193
 194         if (!d) {
 195                 return NULL;
 196         }
 197
 198         if (ldns_rdf_get_type(d) != LDNS_RDF_TYPE_DNAME) {
 199                 return NULL;
 200         }
 201         if (ldns_dname_label_count(d) == 0) {
 202                 /* root label */
 203                 return NULL;
 204         }
 205         /* 05blaat02nl00 */
 206         label_pos = ldns_rdf_data(d)[0];
 207
 208         chop = ldns_dname_new_frm_data(ldns_rdf_size(d) - label_pos - 1,
 209                         ldns_rdf_data(d) + label_pos + 1);
 210         return chop;
 211 }
 212
 213 uint8_t
 214 ldns_dname_label_count(const ldns_rdf *r)
 215 {
 216         uint16_t src_pos;
 217         uint16_t len;
 218         uint8_t i;
 219         size_t r_size;
 220
 221         if (!r) {
 222                 return 0;
 223         }
 224
 225         i = 0;
 226         src_pos = 0;
 227         r_size = ldns_rdf_size(r);
 228
 229         if (ldns_rdf_get_type(r) != LDNS_RDF_TYPE_DNAME) {
 230                 return 0;
 231         } else {
 232                 len = ldns_rdf_data(r)[src_pos]; /* start of the label */
 233
 234                 /* single root label */
 235                 if (1 == r_size) {
 236                         return 0;
 237                 } else {
 238                         while ((len > 0) && src_pos < r_size) {
 239                                 src_pos++;
 240                                 src_pos += len;
 241                                 len = ldns_rdf_data(r)[src_pos];
 242                                 i++;
 243                         }
 244                 }
 245         }
 246         return i;
 247 }
 248
 249 ldns_rdf *
 250 ldns_dname_new(uint16_t s, void *d)
 251 {
 252         ldns_rdf *rd;
 253
 254         if (!s || !d) {
 255                 return NULL;
 256         }
 257         rd = LDNS_MALLOC(ldns_rdf);
 258         if (!rd) {
 259                 return NULL;
 260         }
 261         ldns_rdf_set_size(rd, s);
 262         ldns_rdf_set_type(rd, LDNS_RDF_TYPE_DNAME);
 263         ldns_rdf_set_data(rd, d);
 264         return rd;
 265 }
 266
 267 ldns_rdf *
 268 ldns_dname_new_frm_str(const char *str)
 269 {
 270         return ldns_rdf_new_frm_str(LDNS_RDF_TYPE_DNAME, str);
 271 }
 272
 273 ldns_rdf *
 274 ldns_dname_new_frm_data(uint16_t size, const void *data)
 275 {
 276         return ldns_rdf_new_frm_data(LDNS_RDF_TYPE_DNAME, size, data);
 277 }
 278
 279 void
 280 ldns_dname2canonical(const ldns_rdf *rd)
 281 {
 282         uint8_t *rdd;
 283         uint16_t i;
 284
 285         if (ldns_rdf_get_type(rd) != LDNS_RDF_TYPE_DNAME) {
 286                 return;
 287         }
 288
 289         rdd = (uint8_t*)ldns_rdf_data(rd);
 290         for (i = 0; i < ldns_rdf_size(rd); i++, rdd++) {
 291                 *rdd = (uint8_t)LDNS_DNAME_NORMALIZE((int)*rdd);
 292         }
 293 }
 294
 295 bool
 296 ldns_dname_is_subdomain(const ldns_rdf *sub, const ldns_rdf *parent)
 297 {
 298         uint8_t sub_lab;
 299         uint8_t par_lab;
 300         int8_t i, j;
 301         ldns_rdf *tmp_sub = NULL;
 302         ldns_rdf *tmp_par = NULL;
 303     ldns_rdf *sub_clone;
 304     ldns_rdf *parent_clone;
 305     bool result = true;
 306
 307         if (ldns_rdf_get_type(sub) != LDNS_RDF_TYPE_DNAME ||
 308                         ldns_rdf_get_type(parent) != LDNS_RDF_TYPE_DNAME ||
 309                         ldns_rdf_compare(sub, parent) == 0) {
 310                 return false;
 311         }
 312
 313     /* would be nicer if we do not have to clone... */
 314     sub_clone = ldns_dname_clone_from(sub, 0);
 315     parent_clone = ldns_dname_clone_from(parent, 0);
 316     ldns_dname2canonical(sub_clone);
 317     ldns_dname2canonical(parent_clone);
 318
 319         sub_lab = ldns_dname_label_count(sub_clone);
 320         par_lab = ldns_dname_label_count(parent_clone);
 321
 322         /* if sub sits above parent, it cannot be a child/sub domain */
 323         if (sub_lab < par_lab) {
 324                 result = false;
 325         } else {
 326                 /* check all labels the from the parent labels, from right to left.
 327                  * When they /all/ match we have found a subdomain
 328                  */
 329                 j = sub_lab - 1; /* we count from zero, thank you */
 330                 for (i = par_lab -1; i >= 0; i--) {
 331                         tmp_sub = ldns_dname_label(sub_clone, j);
 332                         tmp_par = ldns_dname_label(parent_clone, i);
 333                         if (!tmp_sub || !tmp_par) {
 334                                 /* deep free does null check */
 335                                 ldns_rdf_deep_free(tmp_sub);
 336                                 ldns_rdf_deep_free(tmp_par);
 337                                 result = false;
 338                                 break;
 339                         }
 340
 341                         if (ldns_rdf_compare(tmp_sub, tmp_par) != 0) {
 342                                 /* they are not equal */
 343                                 ldns_rdf_deep_free(tmp_sub);
 344                                 ldns_rdf_deep_free(tmp_par);
 345                                 result = false;
 346                                 break;
 347                         }
 348                         ldns_rdf_deep_free(tmp_sub);
 349                         ldns_rdf_deep_free(tmp_par);
 350                         j--;
 351                 }
 352         }
 353         ldns_rdf_deep_free(sub_clone);
 354         ldns_rdf_deep_free(parent_clone);
 355         return result;
 356 }
 357
 358 int
 359 ldns_dname_compare(const ldns_rdf *dname1, const ldns_rdf *dname2)
 360 {
 361         size_t lc1, lc2, lc1f, lc2f;
 362         size_t i;
 363         int result = 0;
 364         uint8_t *lp1, *lp2;
 365
 366         /* see RFC4034 for this algorithm */
 367         /* this algorithm assumes the names are normalized to case */
 368
 369         /* only when both are not NULL we can say anything about them */
 370         if (!dname1 && !dname2) {
 371                 return 0;
 372         }
 373         if (!dname1 || !dname2) {
 374                 return -1;
 375         }
 376         /* asserts must happen later as we are looking in the
 377          * dname, which could be NULL. But this case is handled
 378          * above
 379          */
 380         assert(ldns_rdf_get_type(dname1) == LDNS_RDF_TYPE_DNAME);
 381         assert(ldns_rdf_get_type(dname2) == LDNS_RDF_TYPE_DNAME);
 382
 383         lc1 = ldns_dname_label_count(dname1);
 384         lc2 = ldns_dname_label_count(dname2);
 385
 386         if (lc1 == 0 && lc2 == 0) {
 387                 return 0;
 388         }
 389         if (lc1 == 0) {
 390                 return -1;
 391         }
 392         if (lc2 == 0) {
 393                 return 1;
 394         }
 395         lc1--;
 396         lc2--;
 397         /* we start at the last label */
 398         while (true) {
 399                 /* find the label first */
 400                 lc1f = lc1;
 401                 lp1 = ldns_rdf_data(dname1);
 402                 while (lc1f > 0) {
 403                         lp1 += *lp1 + 1;
 404                         lc1f--;
 405                 }
 406
 407                 /* and find the other one */
 408                 lc2f = lc2;
 409                 lp2 = ldns_rdf_data(dname2);
 410                 while (lc2f > 0) {
 411                         lp2 += *lp2 + 1;
 412                         lc2f--;
 413                 }
 414
 415                 /* now check the label character for character. */
 416                 for (i = 1; i < (size_t)(*lp1 + 1); i++) {
 417                         if (i > *lp2) {
 418                                 /* apparently label 1 is larger */
 419                                 result = 1;
 420                                 goto done;
 421                         }
 422                         if (LDNS_DNAME_NORMALIZE((int) *(lp1 + i)) <
 423                             LDNS_DNAME_NORMALIZE((int) *(lp2 + i))) {
 424                             result = -1;
 425                             goto done;
 426                         } else if (LDNS_DNAME_NORMALIZE((int) *(lp1 + i)) >
 427                             LDNS_DNAME_NORMALIZE((int) *(lp2 + i))) {
 428                             result = 1;
 429                             goto done;
 430                         }
 431                 }
 432                 if (*lp1 < *lp2) {
 433                         /* apparently label 2 is larger */
 434                         result = -1;
 435                         goto done;
 436                 }
 437                 if (lc1 == 0 && lc2 > 0) {
 438                         result = -1;
 439                         goto done;
 440                 } else if (lc1 > 0 && lc2 == 0) {
 441                         result = 1;
 442                         goto done;
 443                 } else if (lc1 == 0 && lc2 == 0) {
 444                         result = 0;
 445                         goto done;
 446                 }
 447                 lc1--;
 448                 lc2--;
 449         }
 450
 451         done:
 452         return result;
 453 }
 454
 455 int
 456 ldns_dname_is_wildcard(const ldns_rdf* dname)
 457 {
 458         return ( ldns_dname_label_count(dname) > 0 &&
 459                  ldns_rdf_data(dname)[0] == 1 &&
 460                  ldns_rdf_data(dname)[1] == '*');
 461 }
 462
 463 int
 464 ldns_dname_match_wildcard(const ldns_rdf *dname, const ldns_rdf *wildcard)
 465 {
 466         ldns_rdf *wc_chopped;
 467         int result;
 468         /* check whether it really is a wildcard */
 469         if (ldns_dname_is_wildcard(wildcard)) {
 470                 /* ok, so the dname needs to be a subdomain of the wildcard
 471                  * without the *
 472                  */
 473                 wc_chopped = ldns_dname_left_chop(wildcard);
 474                 result = (int) ldns_dname_is_subdomain(dname, wc_chopped);
 475                 ldns_rdf_deep_free(wc_chopped);
 476         } else {
 477                 result = (ldns_dname_compare(dname, wildcard) == 0);
 478         }
 479         return result;
 480 }
 481
 482 /* nsec test: does prev <= middle < next
 483  * -1 = yes
 484  * 0 = error/can't tell
 485  * 1 = no
 486  */
 487 int
 488 ldns_dname_interval(const ldns_rdf *prev, const ldns_rdf *middle,
 489                 const ldns_rdf *next)
 490 {
 491         int prev_check, next_check;
 492
 493         assert(ldns_rdf_get_type(prev) == LDNS_RDF_TYPE_DNAME);
 494         assert(ldns_rdf_get_type(middle) == LDNS_RDF_TYPE_DNAME);
 495         assert(ldns_rdf_get_type(next) == LDNS_RDF_TYPE_DNAME);
 496
 497         prev_check = ldns_dname_compare(prev, middle);
 498         next_check = ldns_dname_compare(middle, next);
 499         /* <= next. This cannot be the case for nsec, because then we would
 500          * have gotten the nsec of next...
 501          */
 502         if (next_check == 0) {
 503                 return 0;
 504         }
 505
 506                         /* <= */
 507         if ((prev_check == -1 || prev_check == 0) &&
 508                         /* < */
 509                         next_check == -1) {
 510                 return -1;
 511         } else {
 512                 return 1;
 513         }
 514 }
 515
 516
 517 bool
 518 ldns_dname_str_absolute(const char *dname_str)
 519 {
 520         const char* s;
 521         if(dname_str && strcmp(dname_str, ".") == 0)
 522                 return 1;
 523         if(!dname_str || strlen(dname_str) < 2)
 524                 return 0;
 525         if(dname_str[strlen(dname_str) - 1] != '.')
 526                 return 0;
 527         if(dname_str[strlen(dname_str) - 2] != '\\')
 528                 return 1; /* ends in . and no \ before it */
 529         /* so we have the case of ends in . and there is \ before it */
 530         for(s=dname_str; *s; s++) {
 531                 if(*s == '\\') {
 532                         if(s[1] && s[2] && s[3] /* check length */
 533                                 && isdigit((unsigned char)s[1])
 534                                 && isdigit((unsigned char)s[2])
 535                                 && isdigit((unsigned char)s[3]))
 536                                 s += 3;
 537                         else if(!s[1] || isdigit((unsigned char)s[1])) /* escape of nul,0-9 */
 538                                 return 0; /* parse error */
 539                         else s++; /* another character escaped */
 540                 }
 541                 else if(!*(s+1) && *s == '.')
 542                         return 1; /* trailing dot, unescaped */
 543         }
 544         return 0;
 545 }
 546
 547 bool
 548 ldns_dname_absolute(const ldns_rdf *rdf)
 549 {
 550         char *str = ldns_rdf2str(rdf);
 551         if (str) {
 552                 bool r = ldns_dname_str_absolute(str);
 553                 LDNS_FREE(str);
 554                 return r;
 555         }
 556         return false;
 557 }
 558
 559 ldns_rdf *
 560 ldns_dname_label(const ldns_rdf *rdf, uint8_t labelpos)
 561 {
 562         uint8_t labelcnt;
 563         uint16_t src_pos;
 564         uint16_t len;
 565         ldns_rdf *tmpnew;
 566         size_t s;
 567         uint8_t *data;
 568
 569         if (ldns_rdf_get_type(rdf) != LDNS_RDF_TYPE_DNAME) {
 570                 return NULL;
 571         }
 572
 573         labelcnt = 0;
 574         src_pos = 0;
 575         s = ldns_rdf_size(rdf);
 576
 577         len = ldns_rdf_data(rdf)[src_pos]; /* label start */
 578         while ((len > 0) && src_pos < s) {
 579                 if (labelcnt == labelpos) {
 580                         /* found our label */
 581                         data = LDNS_XMALLOC(uint8_t, len + 2);
 582                         if (!data) {
 583                                 return NULL;
 584                         }
 585                         memcpy(data, ldns_rdf_data(rdf) + src_pos, len + 1);
 586                         data[len + 2 - 1] = 0;
 587
 588                         tmpnew = ldns_rdf_new( LDNS_RDF_TYPE_DNAME
 589                                              , len + 2, data);
 590                         if (!tmpnew) {
 591                                 LDNS_FREE(data);
 592                                 return NULL;
 593                         }
 594                         return tmpnew;
 595                 }
 596                 src_pos++;
 597                 src_pos += len;
 598                 len = ldns_rdf_data(rdf)[src_pos];
 599                 labelcnt++;
 600         }
 601         return NULL;
 602 }