nginx/src/core/ngx_resolver.c

   1
   2 /*
   3  * Copyright (C) Igor Sysoev
   4  */
   5
   6
   7 #include <ngx_config.h>
   8 #include <ngx_core.h>
   9 #include <ngx_event.h>
  10
  11
  12 #define NGX_RESOLVER_UDP_SIZE   4096
  13
  14
  15 typedef struct {
  16     u_char  ident_hi;
  17     u_char  ident_lo;
  18     u_char  flags_hi;
  19     u_char  flags_lo;
  20     u_char  nqs_hi;
  21     u_char  nqs_lo;
  22     u_char  nan_hi;
  23     u_char  nan_lo;
  24     u_char  nns_hi;
  25     u_char  nns_lo;
  26     u_char  nar_hi;
  27     u_char  nar_lo;
  28 } ngx_resolver_query_t;
  29
  30
  31 typedef struct {
  32     u_char  type_hi;
  33     u_char  type_lo;
  34     u_char  class_hi;
  35     u_char  class_lo;
  36 } ngx_resolver_qs_t;
  37
  38
  39 typedef struct {
  40     u_char  type_hi;
  41     u_char  type_lo;
  42     u_char  class_hi;
  43     u_char  class_lo;
  44     u_char  ttl[4];
  45     u_char  len_hi;
  46     u_char  len_lo;
  47 } ngx_resolver_an_t;
  48
  49
  50 ngx_int_t ngx_udp_connect(ngx_udp_connection_t *uc);
  51
  52
  53 static void ngx_resolver_cleanup(void *data);
  54 static void ngx_resolver_cleanup_tree(ngx_resolver_t *r, ngx_rbtree_t *tree);
  55 static ngx_int_t ngx_resolve_name_locked(ngx_resolver_t *r,
  56     ngx_resolver_ctx_t *ctx);
  57 static void ngx_resolver_expire(ngx_resolver_t *r, ngx_rbtree_t *tree,
  58     ngx_queue_t *queue);
  59 static ngx_int_t ngx_resolver_send_query(ngx_resolver_t *r,
  60     ngx_resolver_node_t *rn);
  61 static ngx_int_t ngx_resolver_create_name_query(ngx_resolver_node_t *rn,
  62     ngx_resolver_ctx_t *ctx);
  63 static ngx_int_t ngx_resolver_create_addr_query(ngx_resolver_node_t *rn,
  64     ngx_resolver_ctx_t *ctx);
  65 static void ngx_resolver_resend_handler(ngx_event_t *ev);
  66 static time_t ngx_resolver_resend(ngx_resolver_t *r, ngx_rbtree_t *tree,
  67     ngx_queue_t *queue);
  68 static void ngx_resolver_read_response(ngx_event_t *rev);
  69 static void ngx_resolver_process_response(ngx_resolver_t *r, u_char *buf,
  70     size_t n);
  71 static void ngx_resolver_process_a(ngx_resolver_t *r, u_char *buf, size_t n,
  72     ngx_uint_t ident, ngx_uint_t code, ngx_uint_t nan, ngx_uint_t ans);
  73 static void ngx_resolver_process_ptr(ngx_resolver_t *r, u_char *buf, size_t n,
  74     ngx_uint_t ident, ngx_uint_t code, ngx_uint_t nan);
  75 static ngx_resolver_node_t *ngx_resolver_lookup_name(ngx_resolver_t *r,
  76     ngx_str_t *name, uint32_t hash);
  77 static ngx_resolver_node_t *ngx_resolver_lookup_addr(ngx_resolver_t *r,
  78     in_addr_t addr);
  79 static void ngx_resolver_rbtree_insert_value(ngx_rbtree_node_t *temp,
  80     ngx_rbtree_node_t *node, ngx_rbtree_node_t *sentinel);
  81 static ngx_int_t ngx_resolver_copy(ngx_resolver_t *r, ngx_str_t *name,
  82     u_char *buf, u_char *src, u_char *last);
  83 static void ngx_resolver_timeout_handler(ngx_event_t *ev);
  84 static void ngx_resolver_free_node(ngx_resolver_t *r, ngx_resolver_node_t *rn);
  85 static void *ngx_resolver_alloc(ngx_resolver_t *r, size_t size);
  86 static void *ngx_resolver_calloc(ngx_resolver_t *r, size_t size);
  87 static void ngx_resolver_free(ngx_resolver_t *r, void *p);
  88 static void ngx_resolver_free_locked(ngx_resolver_t *r, void *p);
  89 static void *ngx_resolver_dup(ngx_resolver_t *r, void *src, size_t size);
  90
  91
  92 /* STUB: ngx_peer_addr_t * */
  93
  94 ngx_resolver_t *
  95 ngx_resolver_create(ngx_conf_t *cf, ngx_peer_addr_t *addr)
  96 {
  97     ngx_resolver_t        *r;
  98     ngx_pool_cleanup_t    *cln;
  99     ngx_udp_connection_t  *uc;
 100
 101     cln = ngx_pool_cleanup_add(cf->pool, 0);
 102     if (cln == NULL) {
 103         return NULL;
 104     }
 105
 106     cln->handler = ngx_resolver_cleanup;
 107
 108     r = ngx_calloc(sizeof(ngx_resolver_t), cf->log);
 109     if (r == NULL) {
 110         return NULL;
 111     }
 112
 113     cln->data = r;
 114
 115     r->event = ngx_calloc(sizeof(ngx_event_t), cf->log);
 116     if (r->event == NULL) {
 117         return NULL;
 118     }
 119
 120     ngx_rbtree_init(&r->name_rbtree, &r->name_sentinel,
 121                     ngx_resolver_rbtree_insert_value);
 122
 123     ngx_rbtree_init(&r->addr_rbtree, &r->addr_sentinel,
 124                     ngx_rbtree_insert_value);
 125
 126     ngx_queue_init(&r->name_resend_queue);
 127     ngx_queue_init(&r->addr_resend_queue);
 128
 129     ngx_queue_init(&r->name_expire_queue);
 130     ngx_queue_init(&r->addr_expire_queue);
 131
 132     r->event->handler = ngx_resolver_resend_handler;
 133     r->event->data = r;
 134     r->event->log = cf->cycle->new_log;
 135     r->ident = -1;
 136
 137     r->resend_timeout = 5;
 138     r->expire = 30;
 139     r->valid = 300;
 140
 141     r->log = cf->cycle->new_log;
 142     r->log_level = NGX_LOG_ALERT;
 143
 144     if (addr) {
 145         uc = ngx_calloc(sizeof(ngx_udp_connection_t), cf->log);
 146         if (uc == NULL) {
 147             return NULL;
 148         }
 149
 150         r->udp_connection = uc;
 151
 152         uc->sockaddr = addr->sockaddr;
 153         uc->socklen = addr->socklen;
 154         uc->server = addr->name;
 155         uc->log = cf->cycle->new_log;
 156     }
 157
 158     return r;
 159 }
 160
 161
 162 static void
 163 ngx_resolver_cleanup(void *data)
 164 {
 165     ngx_resolver_t  *r = data;
 166
 167     if (r) {
 168         ngx_log_debug0(NGX_LOG_DEBUG_CORE, ngx_cycle->log, 0,
 169                        "cleanup resolver");
 170
 171         ngx_resolver_cleanup_tree(r, &r->name_rbtree);
 172
 173         ngx_resolver_cleanup_tree(r, &r->addr_rbtree);
 174
 175         if (r->event) {
 176             ngx_free(r->event);
 177         }
 178
 179         if (r->udp_connection) {
 180             if (r->udp_connection->connection) {
 181                 ngx_close_connection(r->udp_connection->connection);
 182             }
 183
 184             ngx_free(r->udp_connection);
 185         }
 186
 187         ngx_free(r);
 188     }
 189 }
 190
 191
 192 static void
 193 ngx_resolver_cleanup_tree(ngx_resolver_t *r, ngx_rbtree_t *tree)
 194 {
 195     ngx_resolver_ctx_t   *ctx, *next;
 196     ngx_resolver_node_t  *rn;
 197
 198     while (tree->root != tree->sentinel) {
 199
 200         rn = (ngx_resolver_node_t *) ngx_rbtree_min(tree->root, tree->sentinel);
 201
 202         ngx_queue_remove(&rn->queue);
 203
 204         for (ctx = rn->waiting; ctx; ctx = next) {
 205             next = ctx->next;
 206
 207             if (ctx->event) {
 208                 ngx_resolver_free(r, ctx->event);
 209             }
 210
 211             ngx_resolver_free(r, ctx);
 212         }
 213
 214         ngx_rbtree_delete(tree, &rn->node);
 215
 216         ngx_resolver_free_node(r, rn);
 217     }
 218 }
 219
 220
 221 ngx_resolver_ctx_t *
 222 ngx_resolve_start(ngx_resolver_t *r, ngx_resolver_ctx_t *temp)
 223 {
 224     in_addr_t            addr;
 225     ngx_resolver_ctx_t  *ctx;
 226
 227     if (temp) {
 228         addr = ngx_inet_addr(temp->name.data, temp->name.len);
 229
 230         if (addr != INADDR_NONE) {
 231             temp->resolver = r;
 232             temp->state = NGX_OK;
 233             temp->naddrs = 1;
 234             temp->addrs = &temp->addr;
 235             temp->addr = addr;
 236             temp->quick = 1;
 237
 238             return temp;
 239         }
 240     }
 241
 242     if (r->udp_connection == NULL) {
 243         return NGX_NO_RESOLVER;
 244     }
 245
 246     ctx = ngx_resolver_calloc(r, sizeof(ngx_resolver_ctx_t));
 247
 248     if (ctx) {
 249         ctx->resolver = r;
 250     }
 251
 252     return ctx;
 253 }
 254
 255
 256 ngx_int_t
 257 ngx_resolve_name(ngx_resolver_ctx_t *ctx)
 258 {
 259     ngx_int_t        rc;
 260     ngx_resolver_t  *r;
 261
 262     r = ctx->resolver;
 263
 264     ngx_log_debug1(NGX_LOG_DEBUG_CORE, r->log, 0,
 265                    "resolve: \"%V\"", &ctx->name);
 266
 267     if (ctx->quick) {
 268         ctx->handler(ctx);
 269         return NGX_OK;
 270     }
 271
 272     /* lock name mutex */
 273
 274     rc = ngx_resolve_name_locked(r, ctx);
 275
 276     if (rc == NGX_OK) {
 277         return NGX_OK;
 278     }
 279
 280     /* unlock name mutex */
 281
 282     if (rc == NGX_AGAIN) {
 283         return NGX_OK;
 284     }
 285
 286     /* NGX_ERROR */
 287
 288     if (ctx->event) {
 289         ngx_resolver_free(r, ctx->event);
 290     }
 291
 292     ngx_resolver_free(r, ctx);
 293
 294     return NGX_ERROR;
 295 }
 296
 297
 298 void
 299 ngx_resolve_name_done(ngx_resolver_ctx_t *ctx)
 300 {
 301     uint32_t              hash;
 302     ngx_resolver_t       *r;
 303     ngx_resolver_ctx_t   *w, **p;
 304     ngx_resolver_node_t  *rn;
 305
 306     r = ctx->resolver;
 307
 308     ngx_log_debug1(NGX_LOG_DEBUG_CORE, r->log, 0,
 309                    "resolve name done: %i", ctx->state);
 310
 311     if (ctx->quick) {
 312         return;
 313     }
 314
 315     if (ctx->event && ctx->event->timer_set) {
 316         ngx_del_timer(ctx->event);
 317     }
 318
 319     /* lock name mutex */
 320
 321     if (ctx->state == NGX_AGAIN || ctx->state == NGX_RESOLVE_TIMEDOUT) {
 322
 323         hash = ngx_crc32_short(ctx->name.data, ctx->name.len);
 324
 325         rn = ngx_resolver_lookup_name(r, &ctx->name, hash);
 326
 327         if (rn) {
 328             p = &rn->waiting;
 329             w = rn->waiting;
 330
 331             while (w) {
 332                 if (w == ctx) {
 333                     *p = w->next;
 334
 335                     goto done;
 336                 }
 337
 338                 p = &w->next;
 339                 w = w->next;
 340             }
 341         }
 342
 343         ngx_log_error(NGX_LOG_ALERT, r->log, 0,
 344                       "could not cancel %V resolving", &ctx->name);
 345     }
 346
 347 done:
 348
 349     ngx_resolver_expire(r, &r->name_rbtree, &r->name_expire_queue);
 350
 351     /* unlock name mutex */
 352
 353     /* lock alloc mutex */
 354
 355     if (ctx->event) {
 356         ngx_resolver_free_locked(r, ctx->event);
 357     }
 358
 359     ngx_resolver_free_locked(r, ctx);
 360
 361     /* unlock alloc mutex */
 362 }
 363
 364
 365 /* NGX_RESOLVE_A only */
 366
 367 static ngx_int_t
 368 ngx_resolve_name_locked(ngx_resolver_t *r, ngx_resolver_ctx_t *ctx)
 369 {
 370     uint32_t              hash;
 371     in_addr_t             addr, *addrs;
 372     ngx_int_t             rc;
 373     ngx_uint_t            naddrs;
 374     ngx_resolver_ctx_t   *next;
 375     ngx_resolver_node_t  *rn;
 376
 377     hash = ngx_crc32_short(ctx->name.data, ctx->name.len);
 378
 379     rn = ngx_resolver_lookup_name(r, &ctx->name, hash);
 380
 381     if (rn) {
 382
 383         if (rn->valid >= ngx_time()) {
 384
 385             ngx_log_debug0(NGX_LOG_DEBUG_CORE, r->log, 0, "resolve cached");
 386
 387             ngx_queue_remove(&rn->queue);
 388
 389             rn->expire = ngx_time() + r->expire;
 390
 391             ngx_queue_insert_head(&r->name_expire_queue, &rn->queue);
 392
 393             naddrs = rn->naddrs;
 394
 395             if (naddrs) {
 396
 397                 /* NGX_RESOLVE_A answer */
 398
 399                 if (naddrs != 1) {
 400                     addr = 0;
 401                     addrs = ngx_resolver_dup(r, rn->u.addrs,
 402                                              naddrs * sizeof(in_addr_t));
 403                     if (addrs == NULL) {
 404                         return NGX_ERROR;
 405                     }
 406
 407                 } else {
 408                     addr = rn->u.addr;
 409                     addrs = NULL;
 410                 }
 411
 412                 ctx->next = rn->waiting;
 413                 rn->waiting = NULL;
 414
 415                 /* unlock name mutex */
 416
 417                 do {
 418                     ctx->state = NGX_OK;
 419                     ctx->naddrs = naddrs;
 420                     ctx->addrs = (naddrs == 1) ? &ctx->addr : addrs;
 421                     ctx->addr = addr;
 422                     next = ctx->next;
 423
 424                     ctx->handler(ctx);
 425
 426                     ctx = next;
 427                 } while (ctx);
 428
 429                 if (addrs) {
 430                     ngx_resolver_free(r, addrs);
 431                 }
 432
 433                 return NGX_OK;
 434             }
 435
 436             /* NGX_RESOLVE_CNAME */
 437
 438             if (ctx->recursion++ < NGX_RESOLVER_MAX_RECURSION) {
 439
 440                 ctx->name.len = rn->cnlen;
 441                 ctx->name.data = rn->u.cname;
 442
 443                 return ngx_resolve_name_locked(r, ctx);
 444             }
 445
 446             ctx->next = rn->waiting;
 447             rn->waiting = NULL;
 448
 449             /* unlock name mutex */
 450
 451             do {
 452                 ctx->state = NGX_RESOLVE_NXDOMAIN;
 453                 next = ctx->next;
 454
 455                 ctx->handler(ctx);
 456
 457                 ctx = next;
 458             } while (ctx);
 459
 460             return NGX_OK;
 461         }
 462
 463         if (rn->waiting) {
 464
 465             ctx->next = rn->waiting;
 466             rn->waiting = ctx;
 467
 468             return NGX_AGAIN;
 469         }
 470
 471         ngx_queue_remove(&rn->queue);
 472
 473         /* lock alloc mutex */
 474
 475         ngx_resolver_free_locked(r, rn->query);
 476         rn->query = NULL;
 477
 478         if (rn->cnlen) {
 479             ngx_resolver_free_locked(r, rn->u.cname);
 480         }
 481
 482         if (rn->naddrs > 1) {
 483             ngx_resolver_free_locked(r, rn->u.addrs);
 484         }
 485
 486         /* unlock alloc mutex */
 487
 488     } else {
 489
 490         rn = ngx_resolver_alloc(r, sizeof(ngx_resolver_node_t));
 491         if (rn == NULL) {
 492             return NGX_ERROR;
 493         }
 494
 495         rn->name = ngx_resolver_dup(r, ctx->name.data, ctx->name.len);
 496         if (rn->name == NULL) {
 497             ngx_resolver_free(r, rn);
 498             return NGX_ERROR;
 499         }
 500
 501         rn->node.key = hash;
 502         rn->nlen = (u_short) ctx->name.len;
 503         rn->query = NULL;
 504
 505         ngx_rbtree_insert(&r->name_rbtree, &rn->node);
 506     }
 507
 508     rc = ngx_resolver_create_name_query(rn, ctx);
 509
 510     if (rc == NGX_ERROR) {
 511         goto failed;
 512     }
 513
 514     if (rc == NGX_DECLINED) {
 515         ngx_rbtree_delete(&r->name_rbtree, &rn->node);
 516
 517         ngx_resolver_free(r, rn->query);
 518         ngx_resolver_free(r, rn->name);
 519         ngx_resolver_free(r, rn);
 520
 521         ctx->state = NGX_RESOLVE_NXDOMAIN;
 522         ctx->handler(ctx);
 523
 524         return NGX_OK;
 525     }
 526
 527     if (ngx_resolver_send_query(r, rn) != NGX_OK) {
 528         goto failed;
 529     }
 530
 531     if (ctx->event == NULL) {
 532         ctx->event = ngx_resolver_calloc(r, sizeof(ngx_event_t));
 533         if (ctx->event == NULL) {
 534             goto failed;
 535         }
 536
 537         ctx->event->handler = ngx_resolver_timeout_handler;
 538         ctx->event->data = ctx;
 539         ctx->event->log = r->log;
 540         ctx->ident = -1;
 541
 542         ngx_add_timer(ctx->event, ctx->timeout);
 543     }
 544
 545     if (ngx_queue_empty(&r->name_resend_queue)) {
 546         ngx_add_timer(r->event, (ngx_msec_t) (r->resend_timeout * 1000));
 547     }
 548
 549     rn->expire = ngx_time() + r->resend_timeout;
 550
 551     ngx_queue_insert_head(&r->name_resend_queue, &rn->queue);
 552
 553     rn->cnlen = 0;
 554     rn->naddrs = 0;
 555     rn->valid = 0;
 556     rn->waiting = ctx;
 557
 558     ctx->state = NGX_AGAIN;
 559
 560     return NGX_AGAIN;
 561
 562 failed:
 563
 564     ngx_rbtree_delete(&r->name_rbtree, &rn->node);
 565
 566     if (rn->query) {
 567         ngx_resolver_free(r, rn->query);
 568     }
 569
 570     ngx_resolver_free(r, rn->name);
 571
 572     ngx_resolver_free(r, rn);
 573
 574     return NGX_ERROR;
 575 }
 576
 577
 578 ngx_int_t
 579 ngx_resolve_addr(ngx_resolver_ctx_t *ctx)
 580 {
 581     ngx_resolver_t       *r;
 582     ngx_resolver_node_t  *rn;
 583
 584     r = ctx->resolver;
 585
 586     ctx->addr = ntohl(ctx->addr);
 587
 588     /* lock addr mutex */
 589
 590     rn = ngx_resolver_lookup_addr(r, ctx->addr);
 591
 592     if (rn) {
 593
 594         if (rn->valid >= ngx_time()) {
 595
 596             ngx_log_debug0(NGX_LOG_DEBUG_CORE, r->log, 0, "resolve cached");
 597
 598             ngx_queue_remove(&rn->queue);
 599
 600             rn->expire = ngx_time() + r->expire;
 601
 602             ngx_queue_insert_head(&r->addr_expire_queue, &rn->queue);
 603
 604             ctx->name.len = rn->nlen;
 605             ctx->name.data = ngx_resolver_dup(r, rn->name, rn->nlen);
 606             if (ctx->name.data == NULL) {
 607                 goto failed;
 608             }
 609
 610             /* unlock addr mutex */
 611
 612             ctx->state = NGX_OK;
 613
 614             ctx->handler(ctx);
 615
 616             ngx_resolver_free(r, ctx->name.data);
 617
 618             return NGX_OK;
 619         }
 620
 621         if (rn->waiting) {
 622
 623             ctx->next = rn->waiting;
 624             rn->waiting = ctx;
 625
 626             return NGX_AGAIN;
 627         }
 628
 629         ngx_queue_remove(&rn->queue);
 630
 631         ngx_resolver_free(r, rn->query);
 632         rn->query = NULL;
 633
 634     } else {
 635         rn = ngx_resolver_alloc(r, sizeof(ngx_resolver_node_t));
 636         if (rn == NULL) {
 637             goto failed;
 638         }
 639
 640         rn->node.key = ctx->addr;
 641         rn->query = NULL;
 642
 643         ngx_rbtree_insert(&r->addr_rbtree, &rn->node);
 644     }
 645
 646     if (ngx_resolver_create_addr_query(rn, ctx) != NGX_OK) {
 647         goto failed;
 648     }
 649
 650     if (ngx_resolver_send_query(r, rn) != NGX_OK) {
 651         goto failed;
 652     }
 653
 654     ctx->event = ngx_resolver_calloc(r, sizeof(ngx_event_t));
 655     if (ctx->event == NULL) {
 656         goto failed;
 657     }
 658
 659     ctx->event->handler = ngx_resolver_timeout_handler;
 660     ctx->event->data = ctx;
 661     ctx->event->log = r->log;
 662     ctx->ident = -1;
 663
 664     ngx_add_timer(ctx->event, ctx->timeout);
 665
 666     if (ngx_queue_empty(&r->addr_resend_queue)) {
 667         ngx_add_timer(r->event, (ngx_msec_t) (r->resend_timeout * 1000));
 668     }
 669
 670     rn->expire = ngx_time() + r->resend_timeout;
 671
 672     ngx_queue_insert_head(&r->addr_resend_queue, &rn->queue);
 673
 674     rn->cnlen = 0;
 675     rn->naddrs = 0;
 676     rn->name = NULL;
 677     rn->nlen = 0;
 678     rn->valid = 0;
 679     rn->waiting = ctx;
 680
 681     /* unlock addr mutex */
 682
 683     ctx->state = NGX_AGAIN;
 684
 685     return NGX_OK;
 686
 687 failed:
 688
 689     if (rn) {
 690         ngx_rbtree_delete(&r->addr_rbtree, &rn->node);
 691
 692         if (rn->query) {
 693             ngx_resolver_free(r, rn->query);
 694         }
 695
 696         ngx_resolver_free(r, rn);
 697     }
 698
 699     /* unlock addr mutex */
 700
 701     if (ctx->event) {
 702         ngx_resolver_free(r, ctx->event);
 703     }
 704
 705     ngx_resolver_free(r, ctx);
 706
 707     return NGX_ERROR;
 708 }
 709
 710
 711 void
 712 ngx_resolve_addr_done(ngx_resolver_ctx_t *ctx)
 713 {
 714     in_addr_t             addr;
 715     ngx_resolver_t       *r;
 716     ngx_resolver_ctx_t   *w, **p;
 717     ngx_resolver_node_t  *rn;
 718
 719     r = ctx->resolver;
 720
 721     ngx_log_debug1(NGX_LOG_DEBUG_CORE, r->log, 0,
 722                    "resolve addr done: %i", ctx->state);
 723
 724     if (ctx->event && ctx->event->timer_set) {
 725         ngx_del_timer(ctx->event);
 726     }
 727
 728     /* lock addr mutex */
 729
 730     if (ctx->state == NGX_AGAIN || ctx->state == NGX_RESOLVE_TIMEDOUT) {
 731
 732         rn = ngx_resolver_lookup_addr(r, ctx->addr);
 733
 734         if (rn) {
 735             p = &rn->waiting;
 736             w = rn->waiting;
 737
 738             while (w) {
 739                 if (w == ctx) {
 740                     *p = w->next;
 741
 742                     goto done;
 743                 }
 744
 745                 p = &w->next;
 746                 w = w->next;
 747             }
 748         }
 749
 750         addr = ntohl(ctx->addr);
 751
 752         ngx_log_error(NGX_LOG_ALERT, r->log, 0,
 753                       "could not cancel %ud.%ud.%ud.%ud resolving",
 754                       (addr >> 24) & 0xff, (addr >> 16) & 0xff,
 755                       (addr >> 8) & 0xff, addr & 0xff);
 756     }
 757
 758 done:
 759
 760     ngx_resolver_expire(r, &r->addr_rbtree, &r->addr_expire_queue);
 761
 762     /* unlock addr mutex */
 763
 764     /* lock alloc mutex */
 765
 766     if (ctx->event) {
 767         ngx_resolver_free_locked(r, ctx->event);
 768     }
 769
 770     ngx_resolver_free_locked(r, ctx);
 771
 772     /* unlock alloc mutex */
 773 }
 774
 775
 776 static void
 777 ngx_resolver_expire(ngx_resolver_t *r, ngx_rbtree_t *tree, ngx_queue_t *queue)
 778 {
 779     time_t                now;
 780     ngx_uint_t            i;
 781     ngx_queue_t          *q;
 782     ngx_resolver_node_t  *rn;
 783
 784     ngx_log_debug0(NGX_LOG_DEBUG_CORE, r->log, 0, "resolver expire");
 785
 786     now = ngx_time();
 787
 788     for (i = 0; i < 2; i++) {
 789         if (ngx_queue_empty(queue)) {
 790             return;
 791         }
 792
 793         q = ngx_queue_last(queue);
 794
 795         rn = ngx_queue_data(q, ngx_resolver_node_t, queue);
 796
 797         if (now <= rn->expire) {
 798             return;
 799         }
 800
 801         ngx_log_debug2(NGX_LOG_DEBUG_CORE, r->log, 0,
 802                        "resolver expire \"%*s\"", (size_t) rn->nlen, rn->name);
 803
 804         ngx_queue_remove(q);
 805
 806         ngx_rbtree_delete(tree, &rn->node);
 807
 808         ngx_resolver_free_node(r, rn);
 809     }
 810 }
 811
 812
 813 static ngx_int_t
 814 ngx_resolver_send_query(ngx_resolver_t *r, ngx_resolver_node_t *rn)
 815 {
 816     ssize_t                n;
 817     ngx_udp_connection_t  *uc;
 818
 819     uc = r->udp_connection;
 820
 821     if (uc->connection == NULL) {
 822         if (ngx_udp_connect(uc) != NGX_OK) {
 823             return NGX_ERROR;
 824         }
 825
 826         uc->connection->data = r;
 827         uc->connection->read->handler = ngx_resolver_read_response;
 828         uc->connection->read->resolver = 1;
 829     }
 830
 831     n = ngx_send(uc->connection, rn->query, rn->qlen);
 832
 833     if (n == -1) {
 834         return NGX_ERROR;
 835     }
 836
 837     if ((size_t) n != (size_t) rn->qlen) {
 838         ngx_log_error(NGX_LOG_CRIT, uc->log, 0, "send() incomplete");
 839         return NGX_ERROR;
 840     }
 841
 842     return NGX_OK;
 843 }
 844
 845
 846 static void
 847 ngx_resolver_resend_handler(ngx_event_t *ev)
 848 {
 849     time_t           timer, atimer, ntimer;
 850     ngx_resolver_t  *r;
 851
 852     r = ev->data;
 853
 854     ngx_log_debug0(NGX_LOG_DEBUG_CORE, r->log, 0,
 855                    "resolver resend handler");
 856
 857     /* lock name mutex */
 858
 859     ntimer = ngx_resolver_resend(r, &r->name_rbtree, &r->name_resend_queue);
 860
 861     /* unlock name mutex */
 862
 863     /* lock addr mutex */
 864
 865     atimer = ngx_resolver_resend(r, &r->addr_rbtree, &r->addr_resend_queue);
 866
 867     /* unlock addr mutex */
 868
 869     if (ntimer == 0) {
 870         timer = atimer;
 871
 872     } else if (atimer == 0) {
 873         timer = ntimer;
 874
 875     } else {
 876         timer = (atimer < ntimer) ? atimer : ntimer;
 877     }
 878
 879     if (timer) {
 880         ngx_add_timer(r->event, (ngx_msec_t) (timer * 1000));
 881     }
 882 }
 883
 884
 885 static time_t
 886 ngx_resolver_resend(ngx_resolver_t *r, ngx_rbtree_t *tree, ngx_queue_t *queue)
 887 {
 888     time_t                now;
 889     ngx_queue_t          *q;
 890     ngx_resolver_node_t  *rn;
 891
 892     now = ngx_time();
 893
 894     for ( ;; ) {
 895         if (ngx_queue_empty(queue)) {
 896             return 0;
 897         }
 898
 899         q = ngx_queue_last(queue);
 900
 901         rn = ngx_queue_data(q, ngx_resolver_node_t, queue);
 902
 903         if (now < rn->expire) {
 904             return rn->expire - now;
 905         }
 906
 907         ngx_log_debug3(NGX_LOG_DEBUG_CORE, r->log, 0,
 908                        "resolver resend \"%*s\" %p",
 909                        (size_t) rn->nlen, rn->name, rn->waiting);
 910
 911         ngx_queue_remove(q);
 912
 913         if (rn->waiting) {
 914
 915             if (ngx_resolver_send_query(r, rn) == NGX_OK) {
 916
 917                 rn->expire = now + r->resend_timeout;
 918
 919                 ngx_queue_insert_head(queue, &rn->queue);
 920             }
 921
 922             continue;
 923         }
 924
 925         ngx_rbtree_delete(tree, &rn->node);
 926
 927         ngx_resolver_free_node(r, rn);
 928     }
 929 }
 930
 931
 932 static void
 933 ngx_resolver_read_response(ngx_event_t *rev)
 934 {
 935     ssize_t            n;
 936     ngx_connection_t  *c;
 937     u_char             buf[NGX_RESOLVER_UDP_SIZE];
 938
 939     c = rev->data;
 940
 941     do {
 942         n = ngx_udp_recv(c, buf, NGX_RESOLVER_UDP_SIZE);
 943
 944         if (n < 0) {
 945             return;
 946         }
 947
 948         ngx_resolver_process_response(c->data, buf, n);
 949
 950     } while (rev->ready);
 951 }
 952
 953
 954 static void
 955 ngx_resolver_process_response(ngx_resolver_t *r, u_char *buf, size_t n)
 956 {
 957     char                  *err;
 958     size_t                 len;
 959     ngx_uint_t             i, times, ident, qident, flags, code, nqs, nan,
 960                            qtype, qclass;
 961     ngx_queue_t           *q;
 962     ngx_resolver_qs_t     *qs;
 963     ngx_resolver_node_t   *rn;
 964     ngx_resolver_query_t  *query;
 965
 966     if ((size_t) n < sizeof(ngx_resolver_query_t)) {
 967         goto short_response;
 968     }
 969
 970     query = (ngx_resolver_query_t *) buf;
 971
 972     ident = (query->ident_hi << 8) + query->ident_lo;
 973     flags = (query->flags_hi << 8) + query->flags_lo;
 974     nqs = (query->nqs_hi << 8) + query->nqs_lo;
 975     nan = (query->nan_hi << 8) + query->nan_lo;
 976
 977     ngx_log_debug6(NGX_LOG_DEBUG_CORE, r->log, 0,
 978                    "resolver DNS response %ui fl:%04Xui %ui/%ui/%ui/%ui",
 979                    ident, flags, nqs, nan,
 980                    (query->nns_hi << 8) + query->nns_lo,
 981                    (query->nar_hi << 8) + query->nar_lo);
 982
 983     if (!(flags & 0x8000)) {
 984         ngx_log_error(r->log_level, r->log, 0,
 985                       "invalid DNS response %ui fl:%04Xui", ident, flags);
 986         return;
 987     }
 988
 989     code = flags & 0x7f;
 990
 991     if (code == NGX_RESOLVE_FORMERR) {
 992
 993         times = 0;
 994
 995         for (q = ngx_queue_head(&r->name_resend_queue);
 996              q != ngx_queue_sentinel(&r->name_resend_queue) || times++ < 100;
 997              q = ngx_queue_next(q))
 998         {
 999             rn = ngx_queue_data(q, ngx_resolver_node_t, queue);
1000             qident = (rn->query[0] << 8) + rn->query[1];
1001
1002             if (qident == ident) {
1003                 ngx_log_error(r->log_level, r->log, 0,
1004                               "DNS error (%ui: %s), query id:%ui, name:\"%*s\"",
1005                               code, ngx_resolver_strerror(code), ident,
1006                               rn->nlen, rn->name);
1007                 return;
1008             }
1009         }
1010
1011         goto dns_error;
1012     }
1013
1014     if (code > NGX_RESOLVE_REFUSED) {
1015         goto dns_error;
1016     }
1017
1018     if (nqs != 1) {
1019         err = "invalid number of questions in DNS response";
1020         goto done;
1021     }
1022
1023     i = sizeof(ngx_resolver_query_t);
1024
1025     while (i < (ngx_uint_t) n) {
1026         if (buf[i] == '\0') {
1027             goto found;
1028         }
1029
1030         len = buf[i];
1031         i += 1 + len;
1032     }
1033
1034     goto short_response;
1035
1036 found:
1037
1038     if (i++ == 0) {
1039         err = "zero-length domain name in DNS response";
1040         goto done;
1041     }
1042
1043     if (i + sizeof(ngx_resolver_qs_t) + nan * (2 + sizeof(ngx_resolver_an_t))
1044         > (ngx_uint_t) n)
1045     {
1046         goto short_response;
1047     }
1048
1049     qs = (ngx_resolver_qs_t *) &buf[i];
1050
1051     qtype = (qs->type_hi << 8) + qs->type_lo;
1052     qclass = (qs->class_hi << 8) + qs->class_lo;
1053
1054     ngx_log_debug2(NGX_LOG_DEBUG_CORE, r->log, 0,
1055                    "resolver DNS response qt:%ui cl:%ui", qtype, qclass);
1056
1057     if (qclass != 1) {
1058         ngx_log_error(r->log_level, r->log, 0,
1059                       "unknown query class %ui in DNS response", qclass);
1060         return;
1061     }
1062
1063     switch (qtype) {
1064
1065     case NGX_RESOLVE_A:
1066
1067         ngx_resolver_process_a(r, buf, n, ident, code, nan,
1068                                i + sizeof(ngx_resolver_qs_t));
1069
1070         break;
1071
1072     case NGX_RESOLVE_PTR:
1073
1074         ngx_resolver_process_ptr(r, buf, n, ident, code, nan);
1075
1076         break;
1077
1078     default:
1079         ngx_log_error(r->log_level, r->log, 0,
1080                       "unknown query type %ui in DNS response", qtype);
1081         return;
1082     }
1083
1084     return;
1085
1086 short_response:
1087
1088     err = "short dns response";
1089
1090 done:
1091
1092     ngx_log_error(r->log_level, r->log, 0, err);
1093
1094     return;
1095
1096 dns_error:
1097
1098     ngx_log_error(r->log_level, r->log, 0,
1099                   "DNS error (%ui: %s), query id:%ui",
1100                   code, ngx_resolver_strerror(code), ident);
1101     return;
1102 }
1103
1104
1105 static void
1106 ngx_resolver_process_a(ngx_resolver_t *r, u_char *buf, size_t last,
1107     ngx_uint_t ident, ngx_uint_t code, ngx_uint_t nan, ngx_uint_t ans)
1108 {
1109     char                 *err;
1110     u_char               *cname;
1111     size_t                len;
1112     uint32_t              hash;
1113     in_addr_t             addr, *addrs;
1114     ngx_str_t             name;
1115     ngx_uint_t            qtype, qident, naddrs, a, i, n, start;
1116     ngx_resolver_an_t    *an;
1117     ngx_resolver_ctx_t   *ctx, *next;
1118     ngx_resolver_node_t  *rn;
1119
1120     if (ngx_resolver_copy(r, &name, buf, &buf[12], &buf[last]) != NGX_OK) {
1121         return;
1122     }
1123
1124     ngx_log_debug1(NGX_LOG_DEBUG_CORE, r->log, 0, "resolver qs:%V", &name);
1125
1126     hash = ngx_crc32_short(name.data, name.len);
1127
1128     /* lock name mutex */
1129
1130     rn = ngx_resolver_lookup_name(r, &name, hash);
1131
1132     if (rn == NULL || rn->query == NULL) {
1133         ngx_log_error(r->log_level, r->log, 0,
1134                       "unexpected response for %V", &name);
1135         goto failed;
1136     }
1137
1138     qident = (rn->query[0] << 8) + rn->query[1];
1139
1140     if (ident != qident) {
1141         ngx_log_error(r->log_level, r->log, 0,
1142                       "wrong ident %ui response for %V, expect %ui",
1143                       ident, &name, qident);
1144         goto failed;
1145     }
1146
1147     if (code == 0 && nan == 0) {
1148         code = 3; /* NXDOMAIN */
1149     }
1150
1151     if (code) {
1152         next = rn->waiting;
1153         rn->waiting = NULL;
1154
1155         ngx_queue_remove(&rn->queue);
1156
1157         ngx_rbtree_delete(&r->name_rbtree, &rn->node);
1158
1159         ngx_resolver_free_node(r, rn);
1160
1161         /* unlock name mutex */
1162
1163         while (next) {
1164              ctx = next;
1165              ctx->state = code;
1166              next = ctx->next;
1167
1168              ctx->handler(ctx);
1169         }
1170
1171         return;
1172     }
1173
1174     i = ans;
1175     naddrs = 0;
1176     addr = 0;
1177     addrs = NULL;
1178     cname = NULL;
1179     qtype = 0;
1180
1181     for (a = 0; a < nan; a++) {
1182
1183         start = i;
1184
1185         while (i < last) {
1186
1187             if (buf[i] & 0xc0) {
1188                 i += 2;
1189                 goto found;
1190             }
1191
1192             if (buf[i] == 0) {
1193                 i++;
1194                 goto test_length;
1195             }
1196
1197             i += 1 + buf[i];
1198         }
1199
1200         goto short_response;
1201
1202     test_length:
1203
1204         if (i - start < 2) {
1205             err = "invalid name in dns response";
1206             goto invalid;
1207         }
1208
1209     found:
1210
1211         if (i + sizeof(ngx_resolver_an_t) >= last) {
1212             goto short_response;
1213         }
1214
1215         an = (ngx_resolver_an_t *) &buf[i];
1216
1217         qtype = (an->type_hi << 8) + an->type_lo;
1218         len = (an->len_hi << 8) + an->len_lo;
1219
1220         if (qtype == NGX_RESOLVE_A) {
1221
1222             i += sizeof(ngx_resolver_an_t);
1223
1224             if (i + len > last) {
1225                 goto short_response;
1226             }
1227
1228             addr = htonl((buf[i] << 24) + (buf[i + 1] << 16)
1229                          + (buf[i + 2] << 8) + (buf[i + 3]));
1230
1231             naddrs++;
1232
1233             i += len;
1234
1235         } else if (qtype == NGX_RESOLVE_CNAME) {
1236             cname = &buf[i] + sizeof(ngx_resolver_an_t);
1237             i += sizeof(ngx_resolver_an_t) + len;
1238
1239         } else if (qtype == NGX_RESOLVE_DNAME) {
1240             i += sizeof(ngx_resolver_an_t) + len;
1241
1242         } else {
1243             ngx_log_error(r->log_level, r->log, 0,
1244                           "unexpected qtype %ui", qtype);
1245         }
1246     }
1247
1248     ngx_log_debug2(NGX_LOG_DEBUG_CORE, r->log, 0,
1249                    "resolver naddrs:%ui cname:%p", naddrs, cname);
1250
1251     if (naddrs) {
1252
1253         if (naddrs == 1) {
1254             rn->u.addr = addr;
1255
1256         } else {
1257
1258             addrs = ngx_resolver_alloc(r, naddrs * sizeof(in_addr_t));
1259             if (addrs == NULL) {
1260                 return;
1261             }
1262
1263             n = 0;
1264             i = ans;
1265
1266             for (a = 0; a < nan; a++) {
1267
1268                 for ( ;; ) {
1269
1270                     if (buf[i] & 0xc0) {
1271                         i += 2;
1272                         goto ok;
1273                     }
1274
1275                     if (buf[i] == 0) {
1276                         i++;
1277                         goto ok;
1278                     }
1279
1280                     i += 1 + buf[i];
1281                 }
1282
1283             ok:
1284
1285                 an = (ngx_resolver_an_t *) &buf[i];
1286
1287                 qtype = (an->type_hi << 8) + an->type_lo;
1288                 len = (an->len_hi << 8) + an->len_lo;
1289
1290                 i += sizeof(ngx_resolver_an_t);
1291
1292                 if (qtype == NGX_RESOLVE_A) {
1293
1294                     addrs[n++] = htonl((buf[i] << 24) + (buf[i + 1] << 16)
1295                                        + (buf[i + 2] << 8) + (buf[i + 3]));
1296
1297                     if (n == naddrs) {
1298                         break;
1299                     }
1300                 }
1301
1302                 i += len;
1303             }
1304
1305             rn->u.addrs = addrs;
1306
1307             addrs = ngx_resolver_dup(r, rn->u.addrs,
1308                                      naddrs * sizeof(in_addr_t));
1309             if (addrs == NULL) {
1310                 return;
1311             }
1312         }
1313
1314         rn->naddrs = (u_short) naddrs;
1315
1316         ngx_queue_remove(&rn->queue);
1317
1318         rn->valid = ngx_time() + r->valid;
1319         rn->expire = ngx_time() + r->expire;
1320
1321         ngx_queue_insert_head(&r->name_expire_queue, &rn->queue);
1322
1323         next = rn->waiting;
1324         rn->waiting = NULL;
1325
1326         /* unlock name mutex */
1327
1328         while (next) {
1329              ctx = next;
1330              ctx->state = NGX_OK;
1331              ctx->naddrs = naddrs;
1332              ctx->addrs = (naddrs == 1) ? &ctx->addr : addrs;
1333              ctx->addr = addr;
1334              next = ctx->next;
1335
1336              ctx->handler(ctx);
1337         }
1338
1339         if (naddrs) {
1340             ngx_resolver_free(r, addrs);
1341         }
1342
1343         return;
1344
1345     } else if (cname) {
1346
1347         /* CNAME only */
1348
1349         if (ngx_resolver_copy(r, &name, buf, cname, &buf[last]) != NGX_OK) {
1350             return;
1351         }
1352
1353         ngx_log_debug1(NGX_LOG_DEBUG_CORE, r->log, 0,
1354                        "resolver cname:\"%V\"", &name);
1355
1356         ngx_queue_remove(&rn->queue);
1357
1358         rn->cnlen = (u_short) name.len;
1359         rn->u.cname = name.data;
1360         rn->valid = ngx_time() + r->valid;
1361         rn->expire = ngx_time() + r->expire;
1362
1363         ngx_queue_insert_head(&r->name_expire_queue, &rn->queue);
1364
1365         ctx = rn->waiting;
1366         rn->waiting = NULL;
1367
1368         if (ctx) {
1369             ctx->name = name;
1370
1371             (void) ngx_resolve_name_locked(r, ctx);
1372         }
1373
1374         return;
1375     }
1376
1377     ngx_log_error(r->log_level, r->log, 0,
1378                "no A or CNAME types in DNS responses, unknown query type: %ui",
1379                qtype);
1380     return;
1381
1382 short_response:
1383
1384     err = "short dns response";
1385
1386 invalid:
1387
1388     /* unlock name mutex */
1389
1390     ngx_log_error(r->log_level, r->log, 0, err);
1391
1392     return;
1393
1394 failed:
1395
1396     /* unlock name mutex */
1397
1398     return;
1399 }
1400
1401
1402 static void
1403 ngx_resolver_process_ptr(ngx_resolver_t *r, u_char *buf, size_t n,
1404     ngx_uint_t ident, ngx_uint_t code, ngx_uint_t nan)
1405 {
1406     char                 *err;
1407     size_t                len;
1408     in_addr_t             addr;
1409     ngx_int_t             digit;
1410     ngx_str_t             name;
1411     ngx_uint_t            i, mask, qtype, qclass, qident;
1412     ngx_resolver_an_t    *an;
1413     ngx_resolver_ctx_t   *ctx, *next;
1414     ngx_resolver_node_t  *rn;
1415
1416     if (ngx_resolver_copy(r, NULL, buf, &buf[12], &buf[n]) != NGX_OK) {
1417         goto invalid_in_addr_arpa;
1418     }
1419
1420     addr = 0;
1421     i = 12;
1422
1423     for (mask = 0; mask < 32; mask += 8) {
1424         len = buf[i++];
1425
1426         digit = ngx_atoi(&buf[i], len);
1427         if (digit == NGX_ERROR || digit > 255) {
1428             goto invalid_in_addr_arpa;
1429         }
1430
1431         addr += digit << mask;
1432         i += len;
1433     }
1434
1435     if (ngx_strcmp(&buf[i], "\7in-addr\4arpa") != 0) {
1436         goto invalid_in_addr_arpa;
1437     }
1438
1439     /* lock addr mutex */
1440
1441     rn = ngx_resolver_lookup_addr(r, addr);
1442
1443     if (rn == NULL || rn->query == NULL) {
1444         ngx_log_error(r->log_level, r->log, 0,
1445                       "unexpected response for %ud.%ud.%ud.%ud",
1446                       (addr >> 24) & 0xff, (addr >> 16) & 0xff,
1447                       (addr >> 8) & 0xff, addr & 0xff);
1448         goto failed;
1449     }
1450
1451     qident = (rn->query[0] << 8) + rn->query[1];
1452
1453     if (ident != qident) {
1454         ngx_log_error(r->log_level, r->log, 0,
1455                     "wrong ident %ui response for %ud.%ud.%ud.%ud, expect %ui",
1456                     ident, (addr >> 24) & 0xff, (addr >> 16) & 0xff,
1457                     (addr >> 8) & 0xff, addr & 0xff, qident);
1458         goto failed;
1459     }
1460
1461     if (code == 0 && nan == 0) {
1462         code = 3; /* NXDOMAIN */
1463     }
1464
1465     if (code) {
1466         next = rn->waiting;
1467         rn->waiting = NULL;
1468
1469         ngx_queue_remove(&rn->queue);
1470
1471         ngx_rbtree_delete(&r->addr_rbtree, &rn->node);
1472
1473         ngx_resolver_free_node(r, rn);
1474
1475         /* unlock addr mutex */
1476
1477         while (next) {
1478              ctx = next;
1479              ctx->state = code;
1480              next = ctx->next;
1481
1482              ctx->handler(ctx);
1483         }
1484
1485         return;
1486     }
1487
1488     i += sizeof("\7in-addr\4arpa") + sizeof(ngx_resolver_qs_t);
1489
1490     if (i + 2 + sizeof(ngx_resolver_an_t) > (ngx_uint_t) n) {
1491         goto short_response;
1492     }
1493
1494     /* compression pointer to "XX.XX.XX.XX.in-addr.arpa */
1495
1496     if (buf[i] != 0xc0 || buf[i + 1] != 0x0c) {
1497         err = "invalid in-addr.arpa name in DNS response";
1498         goto invalid;
1499     }
1500
1501     an = (ngx_resolver_an_t *) &buf[i + 2];
1502
1503     qtype = (an->type_hi << 8) + an->type_lo;
1504     qclass = (an->class_hi << 8) + an->class_lo;
1505     len = (an->len_hi << 8) + an->len_lo;
1506
1507     ngx_log_debug3(NGX_LOG_DEBUG_CORE, r->log, 0,
1508                   "resolver qt:%ui cl:%ui len:%uz", qtype, qclass, len);
1509
1510     i += 2 + sizeof(ngx_resolver_an_t);
1511
1512     if (i + len > (ngx_uint_t) n) {
1513         goto short_response;
1514     }
1515
1516     len -= 2;
1517
1518     if (ngx_resolver_copy(r, &name, buf, &buf[i], &buf[n]) != NGX_OK) {
1519         return;
1520     }
1521
1522     ngx_log_debug1(NGX_LOG_DEBUG_CORE, r->log, 0, "resolver an:%V", &name);
1523
1524     if (len != (size_t) rn->nlen || ngx_strncmp(name.data, rn->name, len) != 0)
1525     {
1526         ngx_resolver_free(r, rn->name);
1527         rn->name = name.data;
1528
1529         name.data = ngx_resolver_dup(r, rn->name, len);
1530         if (name.data == NULL) {
1531             goto failed;
1532         }
1533     }
1534
1535     ngx_queue_remove(&rn->queue);
1536
1537     rn->valid = ngx_time() + r->valid;
1538     rn->expire = ngx_time() + r->expire;
1539
1540     ngx_queue_insert_head(&r->addr_expire_queue, &rn->queue);
1541
1542     next = rn->waiting;
1543     rn->waiting = NULL;
1544
1545     /* unlock addr mutex */
1546
1547     while (next) {
1548          ctx = next;
1549          ctx->state = NGX_OK;
1550          ctx->name = name;
1551          next = ctx->next;
1552
1553          ctx->handler(ctx);
1554     }
1555
1556     ngx_resolver_free(r, name.data);
1557
1558     return;
1559
1560 invalid_in_addr_arpa:
1561
1562     ngx_log_error(r->log_level, r->log, 0,
1563                   "invalid in-addr.arpa name in DNS response");
1564     return;
1565
1566 short_response:
1567
1568     err = "short DNS response";
1569
1570 invalid:
1571
1572     /* unlock addr mutex */
1573
1574     ngx_log_error(r->log_level, r->log, 0, err);
1575
1576     return;
1577
1578 failed:
1579
1580     /* unlock addr mutex */
1581
1582     return;
1583 }
1584
1585
1586 static ngx_resolver_node_t *
1587 ngx_resolver_lookup_name(ngx_resolver_t *r, ngx_str_t *name, uint32_t hash)
1588 {
1589     ngx_int_t             rc;
1590     size_t                len;
1591     ngx_rbtree_node_t    *node, *sentinel;
1592     ngx_resolver_node_t  *rn;
1593
1594     node = r->name_rbtree.root;
1595     sentinel = r->name_rbtree.sentinel;
1596
1597     while (node != sentinel) {
1598
1599         if (hash < node->key) {
1600             node = node->left;
1601             continue;
1602         }
1603
1604         if (hash > node->key) {
1605             node = node->right;
1606             continue;
1607         }
1608
1609         /* hash == node->key */
1610
1611         do {
1612             rn = (ngx_resolver_node_t *) node;
1613
1614             len = (name->len > (size_t) rn->nlen) ? rn->nlen : name->len;
1615
1616             rc = ngx_strncmp(name->data, rn->name, len);
1617
1618             if (rc == 0) {
1619                 return rn;
1620             }
1621
1622             node = (rc < 0) ? node->left : node->right;
1623
1624         } while (node != sentinel && hash == node->key);
1625
1626         break;
1627     }
1628
1629     /* not found */
1630
1631     return NULL;
1632 }
1633
1634
1635 static ngx_resolver_node_t *
1636 ngx_resolver_lookup_addr(ngx_resolver_t *r, in_addr_t addr)
1637 {
1638     ngx_rbtree_node_t  *node, *sentinel;
1639
1640     node = r->addr_rbtree.root;
1641     sentinel = r->addr_rbtree.sentinel;
1642
1643     while (node != sentinel) {
1644
1645         if (addr < node->key) {
1646             node = node->left;
1647             continue;
1648         }
1649
1650         if (addr > node->key) {
1651             node = node->right;
1652             continue;
1653         }
1654
1655         /* addr == node->key */
1656
1657         return (ngx_resolver_node_t *) node;
1658     }
1659
1660     /* not found */
1661
1662     return NULL;
1663 }
1664
1665
1666 static void
1667 ngx_resolver_rbtree_insert_value(ngx_rbtree_node_t *temp,
1668     ngx_rbtree_node_t *node, ngx_rbtree_node_t *sentinel)
1669 {
1670     size_t                 len;
1671     ngx_rbtree_node_t    **p;
1672     ngx_resolver_node_t   *rn, *rn_temp;
1673
1674     for ( ;; ) {
1675
1676         if (node->key < temp->key) {
1677
1678             p = &temp->left;
1679
1680         } else if (node->key > temp->key) {
1681
1682             p = &temp->right;
1683
1684         } else { /* node->key == temp->key */
1685
1686             rn = (ngx_resolver_node_t *) node;
1687             rn_temp = (ngx_resolver_node_t *) temp;
1688
1689             len = (rn->nlen > rn_temp->nlen) ? rn_temp->nlen : rn->nlen;
1690
1691             p = (ngx_strncmp(rn->name, rn_temp->name, len) < 0)
1692                     ? &temp->left : &temp->right;
1693         }
1694
1695         if (*p == sentinel) {
1696             break;
1697         }
1698
1699         temp = *p;
1700     }
1701
1702     *p = node;
1703     node->parent = temp;
1704     node->left = sentinel;
1705     node->right = sentinel;
1706     ngx_rbt_red(node);
1707 }
1708
1709
1710 static ngx_int_t
1711 ngx_resolver_create_name_query(ngx_resolver_node_t *rn, ngx_resolver_ctx_t *ctx)
1712 {
1713     u_char                *p, *s;
1714     size_t                 len;
1715     ngx_uint_t             ident;
1716     ngx_resolver_qs_t     *qs;
1717     ngx_resolver_query_t  *query;
1718
1719     len = sizeof(ngx_resolver_query_t)
1720           + 1 + ctx->name.len + 1 + sizeof(ngx_resolver_qs_t);
1721
1722     p = ngx_resolver_calloc(ctx->resolver, len);
1723     if (p == NULL) {
1724         return NGX_ERROR;
1725     }
1726
1727     rn->qlen = (u_short) len;
1728     rn->query = p;
1729
1730     query = (ngx_resolver_query_t *) p;
1731
1732     ident = ngx_random();
1733
1734     ngx_log_debug2(NGX_LOG_DEBUG_CORE, ctx->resolver->log, 0,
1735                    "resolve: \"%V\" %i", &ctx->name, ident & 0xffff);
1736
1737     query->ident_hi = (u_char) ((ident >> 8) & 0xff);
1738     query->ident_lo = (u_char) (ident & 0xff);
1739
1740     /* recursion query */
1741     query->flags_hi = 1; query->flags_lo = 0;
1742
1743     /* one question */
1744     query->nqs_hi = 0; query->nqs_lo = 1;
1745     query->nan_hi = 0; query->nan_lo = 0;
1746     query->nns_hi = 0; query->nns_lo = 0;
1747     query->nar_hi = 0; query->nar_lo = 0;
1748
1749     p += sizeof(ngx_resolver_query_t) + 1 + ctx->name.len + 1;
1750
1751     qs = (ngx_resolver_qs_t *) p;
1752
1753     /* query type */
1754     qs->type_hi = 0; qs->type_lo = (u_char) ctx->type;
1755
1756     /* IP query class */
1757     qs->class_hi = 0; qs->class_lo = 1;
1758
1759     /* convert "www.example.com" to "\3www\7example\3com\0" */
1760
1761     len = 0;
1762     p--;
1763     *p-- = '\0';
1764
1765     for (s = ctx->name.data + ctx->name.len - 1; s >= ctx->name.data; s--) {
1766         if (*s != '.') {
1767             *p = *s;
1768             len++;
1769
1770         } else {
1771             if (len == 0) {
1772                 return NGX_DECLINED;
1773             }
1774
1775             *p = (u_char) len;
1776             len = 0;
1777         }
1778
1779         p--;
1780     }
1781
1782     *p = (u_char) len;
1783
1784     return NGX_OK;
1785 }
1786
1787
1788 /* AF_INET only */
1789
1790 static ngx_int_t
1791 ngx_resolver_create_addr_query(ngx_resolver_node_t *rn, ngx_resolver_ctx_t *ctx)
1792 {
1793     u_char                *p, *d;
1794     size_t                 len;
1795     ngx_int_t              n;
1796     ngx_uint_t             ident;
1797     ngx_resolver_query_t  *query;
1798
1799     len = sizeof(ngx_resolver_query_t)
1800           + sizeof(".255.255.255.255.in-addr.arpa.") - 1
1801           + sizeof(ngx_resolver_qs_t);
1802
1803     p = ngx_resolver_calloc(ctx->resolver, len);
1804     if (p == NULL) {
1805         return NGX_ERROR;
1806     }
1807
1808     rn->query = p;
1809     query = (ngx_resolver_query_t *) p;
1810
1811     ident = ngx_random();
1812
1813     query->ident_hi = (u_char) ((ident >> 8) & 0xff);
1814     query->ident_lo = (u_char) (ident & 0xff);
1815
1816     /* recursion query */
1817     query->flags_hi = 1; query->flags_lo = 0;
1818
1819     /* one question */
1820     query->nqs_hi = 0; query->nqs_lo = 1;
1821     query->nan_hi = 0; query->nan_lo = 0;
1822     query->nns_hi = 0; query->nns_lo = 0;
1823     query->nar_hi = 0; query->nar_lo = 0;
1824
1825     p += sizeof(ngx_resolver_query_t);
1826
1827     for (n = 0; n < 32; n += 8){
1828         d = ngx_sprintf(&p[1], "%ud", (ctx->addr >> n) & 0xff);
1829         *p = (u_char) (d - &p[1]);
1830         p = d;
1831     }
1832
1833     /* query type "PTR", IP query class */
1834     ngx_memcpy(p, "\7in-addr\4arpa\0\0\14\0\1", 18);
1835
1836     rn->qlen = (u_short)
1837                   (p + sizeof("\7in-addr\4arpa") + sizeof(ngx_resolver_qs_t)
1838                    - rn->query);
1839
1840     return NGX_OK;
1841 }
1842
1843
1844 static ngx_int_t
1845 ngx_resolver_copy(ngx_resolver_t *r, ngx_str_t *name, u_char *buf, u_char *src,
1846     u_char *last)
1847 {
1848     char        *err;
1849     u_char      *p, *dst;
1850     ssize_t      len;
1851     ngx_uint_t   i, n;
1852
1853     p = src;
1854     len = -1;
1855
1856     /*
1857      * compression pointers allow to create endless loop, so we set limit;
1858      * 128 pointers should be enough to store 255-byte name
1859      */
1860
1861     for (i = 0; i < 128; i++) {
1862         n = *p++;
1863
1864         if (n == 0) {
1865             goto done;
1866         }
1867
1868         if (n & 0xc0) {
1869             n = ((n & 0x3f) << 8) + *p;
1870             p = &buf[n];
1871
1872         } else {
1873             len += 1 + n;
1874             p = &p[n];
1875         }
1876
1877         if (p >= last) {
1878             err = "name is out of response";
1879             goto invalid;
1880         }
1881     }
1882
1883     err = "compression pointers loop";
1884
1885 invalid:
1886
1887     ngx_log_error(r->log_level, r->log, 0, err);
1888
1889     return NGX_ERROR;
1890
1891 done:
1892
1893     if (name == NULL) {
1894         return NGX_OK;
1895     }
1896
1897     dst = ngx_resolver_alloc(r, len);
1898     if (dst == NULL) {
1899         return NGX_ERROR;
1900     }
1901
1902     name->data = dst;
1903
1904     n = *src++;
1905
1906     for ( ;; ) {
1907         if (n != 0xc0) {
1908             ngx_memcpy(dst, src, n);
1909             dst += n;
1910             src += n;
1911
1912             n = *src++;
1913
1914             if (n != 0) {
1915                 *dst++ = '.';
1916             }
1917
1918         } else {
1919             n = ((n & 0x3f) << 8) + *src;
1920             src = &buf[n];
1921
1922             n = *src++;
1923         }
1924
1925         if (n == 0) {
1926             name->len = dst - name->data;
1927             return NGX_OK;
1928         }
1929     }
1930 }
1931
1932
1933 static void
1934 ngx_resolver_timeout_handler(ngx_event_t *ev)
1935 {
1936     ngx_resolver_ctx_t  *ctx;
1937
1938     ctx = ev->data;
1939
1940     ctx->state = NGX_RESOLVE_TIMEDOUT;
1941
1942     ctx->handler(ctx);
1943 }
1944
1945
1946 static void
1947 ngx_resolver_free_node(ngx_resolver_t *r, ngx_resolver_node_t *rn)
1948 {
1949     /* lock alloc mutex */
1950
1951     if (rn->query) {
1952         ngx_resolver_free_locked(r, rn->query);
1953     }
1954
1955     if (rn->name) {
1956         ngx_resolver_free_locked(r, rn->name);
1957     }
1958
1959     if (rn->cnlen) {
1960         ngx_resolver_free_locked(r, rn->u.cname);
1961     }
1962
1963     if (rn->naddrs > 1) {
1964         ngx_resolver_free_locked(r, rn->u.addrs);
1965     }
1966
1967     ngx_resolver_free_locked(r, rn);
1968
1969     /* unlock alloc mutex */
1970 }
1971
1972
1973 static void *
1974 ngx_resolver_alloc(ngx_resolver_t *r, size_t size)
1975 {
1976     u_char  *p;
1977
1978     /* lock alloc mutex */
1979
1980     p = ngx_alloc(size, r->log);
1981
1982     /* unlock alloc mutex */
1983
1984     return p;
1985 }
1986
1987
1988 static void *
1989 ngx_resolver_calloc(ngx_resolver_t *r, size_t size)
1990 {
1991     u_char  *p;
1992
1993     p = ngx_resolver_alloc(r, size);
1994
1995     if (p) {
1996         ngx_memzero(p, size);
1997     }
1998
1999     return p;
2000 }
2001
2002
2003 static void
2004 ngx_resolver_free(ngx_resolver_t *r, void *p)
2005 {
2006     /* lock alloc mutex */
2007
2008     ngx_free(p);
2009
2010     /* unlock alloc mutex */
2011 }
2012
2013
2014 static void
2015 ngx_resolver_free_locked(ngx_resolver_t *r, void *p)
2016 {
2017     ngx_free(p);
2018 }
2019
2020
2021 static void *
2022 ngx_resolver_dup(ngx_resolver_t *r, void *src, size_t size)
2023 {
2024     void  *dst;
2025
2026     dst = ngx_resolver_alloc(r, size);
2027
2028     if (dst == NULL) {
2029         return dst;
2030     }
2031
2032     ngx_memcpy(dst, src, size);
2033
2034     return dst;
2035 }
2036
2037
2038 char *
2039 ngx_resolver_strerror(ngx_int_t err)
2040 {
2041     static char *errors[] = {
2042         "Format error",     /* FORMERR */
2043         "Server failure",   /* SERVFAIL */
2044         "Host not found",   /* NXDOMAIN */
2045         "Unimplemented",    /* NOTIMP */
2046         "Operation refused" /* REFUSED */
2047     };
2048
2049     if (err > 0 && err < 6) {
2050         return errors[err - 1];
2051     }
2052
2053     if (err == NGX_RESOLVE_TIMEDOUT) {
2054         return "Operation timed out";
2055     }
2056
2057     return "Unknown error";
2058 }
2059
2060
2061 ngx_int_t
2062 ngx_udp_connect(ngx_udp_connection_t *uc)
2063 {
2064     int                rc;
2065     ngx_int_t          event;
2066     ngx_event_t       *rev, *wev;
2067     ngx_socket_t       s;
2068     ngx_connection_t  *c;
2069
2070     s = ngx_socket(AF_INET, SOCK_DGRAM, 0);
2071
2072     ngx_log_debug1(NGX_LOG_DEBUG_EVENT, uc->log, 0, "UDP socket %d", s);
2073
2074     if (s == -1) {
2075         ngx_log_error(NGX_LOG_ALERT, uc->log, ngx_socket_errno,
2076                       ngx_socket_n " failed");
2077         return NGX_ERROR;
2078     }
2079
2080     c = ngx_get_connection(s, uc->log);
2081
2082     if (c == NULL) {
2083         if (ngx_close_socket(s) == -1) {
2084             ngx_log_error(NGX_LOG_ALERT, uc->log, ngx_socket_errno,
2085                           ngx_close_socket_n "failed");
2086         }
2087
2088         return NGX_ERROR;
2089     }
2090
2091     if (ngx_nonblocking(s) == -1) {
2092         ngx_log_error(NGX_LOG_ALERT, uc->log, ngx_socket_errno,
2093                       ngx_nonblocking_n " failed");
2094
2095         ngx_free_connection(c);
2096
2097         if (ngx_close_socket(s) == -1) {
2098             ngx_log_error(NGX_LOG_ALERT, uc->log, ngx_socket_errno,
2099                           ngx_close_socket_n " failed");
2100         }
2101
2102         return NGX_ERROR;
2103     }
2104
2105     rev = c->read;
2106     wev = c->write;
2107
2108     rev->log = uc->log;
2109     wev->log = uc->log;
2110
2111     uc->connection = c;
2112
2113     c->number = ngx_atomic_fetch_add(ngx_connection_counter, 1);
2114
2115 #if (NGX_THREADS)
2116
2117     /* TODO: lock event when call completion handler */
2118
2119     rev->lock = &c->lock;
2120     wev->lock = &c->lock;
2121     rev->own_lock = &c->lock;
2122     wev->own_lock = &c->lock;
2123
2124 #endif
2125
2126     ngx_log_debug3(NGX_LOG_DEBUG_EVENT, uc->log, 0,
2127                    "connect to %V, fd:%d #%d", &uc->server, s, c->number);
2128
2129     rc = connect(s, uc->sockaddr, uc->socklen);
2130
2131     /* TODO: aio, iocp */
2132
2133     if (rc == -1) {
2134         ngx_log_error(NGX_LOG_CRIT, uc->log, ngx_socket_errno,
2135                       "connect() to %V failed", &uc->server);
2136
2137         return NGX_ERROR;
2138     }
2139
2140     /* UDP sockets are always ready to write */
2141     wev->ready = 1;
2142
2143     if (ngx_add_event) {
2144
2145         event = (ngx_event_flags & NGX_USE_CLEAR_EVENT) ?
2146                     /* kqueue, epoll */                 NGX_CLEAR_EVENT:
2147                     /* select, poll, /dev/poll */       NGX_LEVEL_EVENT;
2148                     /* eventport event type has no meaning: oneshot only */
2149
2150         if (ngx_add_event(rev, NGX_READ_EVENT, event) != NGX_OK) {
2151             return NGX_ERROR;
2152         }
2153
2154     } else {
2155         /* rtsig */
2156
2157         if (ngx_add_conn(c) == NGX_ERROR) {
2158             return NGX_ERROR;
2159         }
2160     }
2161
2162     return NGX_OK;
2163 }