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