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