From 0e45654b30d8dd31eb4ab9f32ca0bbee7d1c2c6d Mon Sep 17 00:00:00 2001 From: ian Date: Thu, 6 Apr 2006 18:39:44 +0000 Subject: [PATCH] srv with postsort seems to work --- regress/hcommon.c | 3 ++ regress/hcommon.c.m4 | 5 +++ regress/hredirect.h | 2 ++ regress/hsyscalls.h | 1 + regress/hsyscalls.i4 | 1 + src/internal.h | 3 +- src/setup.c | 6 ++++ src/types.c | 79 +++++++++++++++++++++++++++++++++++++++----- 8 files changed, 91 insertions(+), 9 deletions(-) diff --git a/regress/hcommon.c b/regress/hcommon.c index ff984fe..0324e58 100644 --- a/regress/hcommon.c +++ b/regress/hcommon.c @@ -295,3 +295,6 @@ void Hexit(int rv) { } exit(rv); } +pid_t Hgetpid(void) { + return 2264; /* just some number */ +} diff --git a/regress/hcommon.c.m4 b/regress/hcommon.c.m4 index 05ce3f4..d31ad90 100644 --- a/regress/hcommon.c.m4 +++ b/regress/hcommon.c.m4 @@ -315,3 +315,8 @@ void Hexit(int rv) { } exit(rv); } + +pid_t Hgetpid(void) { + return 2264; /* just some number */ +} + diff --git a/regress/hredirect.h b/regress/hredirect.h index fd2fa40..7bff129 100644 --- a/regress/hredirect.h +++ b/regress/hredirect.h @@ -31,6 +31,8 @@ #define writev Hwritev #undef gettimeofday #define gettimeofday Hgettimeofday +#undef getpid +#define getpid Hgetpid #undef malloc #define malloc Hmalloc #undef free diff --git a/regress/hsyscalls.h b/regress/hsyscalls.h index 3e886be..6dc9edc 100644 --- a/regress/hsyscalls.h +++ b/regress/hsyscalls.h @@ -24,6 +24,7 @@ int Hread( int fd , void *buf , size_t buflen ); int Hwrite( int fd , const void *buf , size_t len ); int Hwritev(int fd, const struct iovec *vector, size_t count); int Hgettimeofday(struct timeval *tv, struct timezone *tz); +pid_t Hgetpid(void); void* Hmalloc(size_t sz); void Hfree(void *ptr); void* Hrealloc(void *op, size_t nsz); diff --git a/regress/hsyscalls.i4 b/regress/hsyscalls.i4 index 6be9556..cf9f958 100644 --- a/regress/hsyscalls.i4 +++ b/regress/hsyscalls.i4 @@ -135,6 +135,7 @@ hm_syscall( hm_specsyscall(int, writev, `int fd, const struct iovec *vector, size_t count') hm_specsyscall(int, gettimeofday, `struct timeval *tv, struct timezone *tz') +hm_specsyscall(pid_t, getpid, `void') hm_specsyscall(void*, malloc, `size_t sz') hm_specsyscall(void, free, `void *ptr') diff --git a/src/internal.h b/src/internal.h index 5559229..e4ec09e 100644 --- a/src/internal.h +++ b/src/internal.h @@ -159,7 +159,7 @@ typedef struct typeinfo { * string. On successful return, label_r[] and *ll_io are filled in * and *p_io points to *pe or just after the label-ending `.'. */ - void (*postsort)(adns_state ads, void *array, int nobjs, + void (*postsort)(adns_state ads, void *array, int nrrs, const struct typeinfo *typei); /* Called immediately after the RRs have been sorted, and may rearrange * them. (This is really for the benefit of SRV's bizarre weighting @@ -337,6 +337,7 @@ struct adns__state { struct in_addr base, mask; } sortlist[MAXSORTLIST]; char **searchlist; + unsigned short rand48xsubi[3]; }; /* From setup.c: */ diff --git a/src/setup.c b/src/setup.c index 0134680..64949e1 100644 --- a/src/setup.c +++ b/src/setup.c @@ -509,6 +509,7 @@ int adns__setnonblock(adns_state ads, int fd) { static int init_begin(adns_state *ads_r, adns_initflags flags, adns_logcallbackfn *logfn, void *logfndata) { adns_state ads; + pid_t pid; ads= malloc(sizeof(*ads)); if (!ads) return errno; @@ -532,6 +533,11 @@ static int init_begin(adns_state *ads_r, adns_initflags flags, timerclear(&ads->tcptimeout); ads->searchlist= 0; + pid= getpid(); + ads->rand48xsubi[0]= pid; + ads->rand48xsubi[1]= (unsigned long)pid >> 16; + ads->rand48xsubi[2]= pid ^ ((unsigned long)pid >> 16); + *ads_r= ads; return 0; } diff --git a/src/types.c b/src/types.c index 966f570..d39e341 100644 --- a/src/types.c +++ b/src/types.c @@ -1037,8 +1037,8 @@ static adns_status qdpl_srv(adns_state ads, } static adns_status pap_srv_begin(const parseinfo *pai, int *cbyte_io, int max, - adns_rr_srvraw *rrp - /* might be adns_rr_srvha* */) { + adns_rr_srvha *rrp + /* might be adns_rr_srvraw* */) { const byte *dgram= pai->dgram; int ti, cbyte; @@ -1097,8 +1097,8 @@ static int di_srv(adns_state ads, const void *datap_a, const void *datap_b) { return 0; } -static adns_status csp_srv_begin(vbuf *vb, const adns_rr_srvraw *rrp - /* might be adns_rr_srvha* */) { +static adns_status csp_srv_begin(vbuf *vb, const adns_rr_srvha *rrp + /* might be adns_rr_srvraw* */) { char buf[30]; sprintf(buf,"%u %u %u ", rrp->priority, rrp->weight, rrp->port); CSP_ADDSTR(buf); @@ -1109,7 +1109,7 @@ static adns_status cs_srvraw(vbuf *vb, const void *datap) { const adns_rr_srvraw *rrp= datap; adns_status st; - st= csp_srv_begin(vb,rrp); if (st) return st; + st= csp_srv_begin(vb,(const void*)rrp); if (st) return st; return csp_domain(vb,rrp->host); } @@ -1117,13 +1117,76 @@ static adns_status cs_srvha(vbuf *vb, const void *datap) { const adns_rr_srvha *rrp= datap; adns_status st; - st= csp_srv_begin(vb,datap); if (st) return st; + st= csp_srv_begin(vb,(const void*)datap); if (st) return st; return csp_hostaddr(vb,&rrp->ha); } -static void postsort_srv(adns_state ads, void *array, int nobjs, +static void postsort_srv(adns_state ads, void *array, int nrrs, const struct typeinfo *typei) { - fprintf(stderr,"(postsort_srv)\n"); + /* we treat everything in the array as if it were an adns_rr_srvha + * even though the array might be of adns_rr_srvraw. That's OK + * because they have the same prefix, which is all we access. + * We use typei->rrsz, too, rather than naive array indexing, of course. + */ + char *workbegin, *workend, *search, *arrayend; + const adns_rr_srvha *rr; + union { adns_rr_srvha ha; adns_rr_srvraw raw; } rrtmp; + int cpriority, totalweight, runtotal; + long randval; + + for (workbegin= array, arrayend= workbegin + typei->rrsz * nrrs; + workbegin < arrayend; + workbegin= workend) { + cpriority= (rr=(void*)workbegin)->priority; + + for (workend= workbegin, totalweight= 0; + workend < arrayend && (rr=(void*)workend)->priority == cpriority; + workend += typei->rrsz) { + totalweight += rr->weight; +fprintf(stderr,"(postsort_srv priority %d weight %d)\n", + cpriority, rr->weight); + } + + /* Now workbegin..(workend-1) incl. are exactly all of the RRs of + * cpriority. From now on, workbegin points to the `remaining' + * records: we select one record at a time (RFC2782 `Usage rules' + * and `Format of the SRV RR' subsection `Weight') to place at + * workbegin (swapping with the one that was there, and then + * advance workbegin. */ + for (; + workbegin + typei->rrsz < workend; /* don't bother if just one */ + workbegin += typei->rrsz) { + + randval= nrand48(ads->rand48xsubi); + randval %= (totalweight + 1); +fprintf(stderr,"(postsort_srv totalweight %d randval %ld %ld..%ld<%ld)\n", + totalweight,randval, + (unsigned long)(workbegin - (char*)array) / typei->rrsz, + (unsigned long)(workend - (char*)array) / typei->rrsz, + (unsigned long)(arrayend - (char*)array) / typei->rrsz + ); + /* makes it into 0..totalweight inclusive; with 2^10 RRs, + * totalweight must be <= 2^26 so probability nonuniformity is + * no worse than 1 in 2^(31-26) ie 1 in 2^5, ie + * abs(log(P_intended(RR_i) / P_actual(RR_i)) <= log(2^-5). + */ + + for (search=workbegin, runtotal=0; + (runtotal += (rr=(void*)search)->weight) < randval; + search += typei->rrsz); +fprintf(stderr,"(postsort_srv search %ld runtotal %d)\n", + (unsigned long)(search - (char*)array) / typei->rrsz, + runtotal + ); + assert(search < arrayend); + totalweight -= rr->weight; + if (search != workbegin) { + memcpy(&rrtmp, workbegin, typei->rrsz); + memcpy(workbegin, search, typei->rrsz); + memcpy(search, &rrtmp, typei->rrsz); + } + } + } /* tests: * dig -t srv _srv._tcp.test.iwj.relativity.greenend.org.uk. * ./adnshost_s -t srv- _sip._udp.voip.net.cam.ac.uk. -- 2.30.2