From efd4fb69bbfff4a39206c8d4d1902378363ce14e Mon Sep 17 00:00:00 2001 From: Ken Raeburn Date: Mon, 21 Jun 1999 18:33:05 +0000 Subject: [PATCH] DNS lookup implementation, conditionally compiled under KRB5_DNS_LOOKUP (which is not defined). Written by Ken Hornstein and Jeffrey Altman, with some minor changes from me. git-svn-id: svn://anonsvn.mit.edu/krb5/trunk@11525 dc483132-0cff-0310-8789-dd5450dbe970 --- src/lib/krb5/os/ChangeLog | 33 +++ src/lib/krb5/os/def_realm.c | 63 +++++- src/lib/krb5/os/hst_realm.c | 213 ++++++++++++++++-- src/lib/krb5/os/locate_kdc.c | 425 +++++++++++++++++++++++++++++++++-- 4 files changed, 691 insertions(+), 43 deletions(-) diff --git a/src/lib/krb5/os/ChangeLog b/src/lib/krb5/os/ChangeLog index c493db665..eb89a59a2 100644 --- a/src/lib/krb5/os/ChangeLog +++ b/src/lib/krb5/os/ChangeLog @@ -1,3 +1,36 @@ +1999-06-21 Ken Raeburn + and Jeffrey Altman and Ken Hornstein + + * def_realm.c (MAXHOSTNAMELEN) [KRB5_DNS_LOOKUP]: Define if not + already defined. + (MAX_DNS_NAMELEN) [KRB5_DNS_LOOKUP]: New macro. + (krb5_get_default_realm): Return an error if an empty realm name + is found. + (krb5_get_default_realm) [KRB5_DNS_LOOKUP]: Use + krb5_try_realm_txt_rr to determine the realm of the local host or + domain. + + * hst_realm.c [KRB5_DNS_LOOKUP]: Pull in some extra header files + for resolver functionality. + (MAX_DNS_NAMELEN): New macro. + (krb5_try_realm_txt_rr) [KRB5_DNS_LOOKUP]: New function; looks up + a TXT record. + (krb5_get_host_realm): Use MAX_DNS_NAMELEN for buffer size. + (krb5_get_host_realm) [KRB5_DNS_LOOKUP]: Use DNS lookup if config + file doesn't contain a match. + + * locate_kdc.c [KRB5_DNS_LOOKUP]: Pull in some extra header files + for resolver functionality. + (MAXHOSTNAMELEN) [KRB5_DNS_LOOKUP]: Define if not already + defined. + (MAX_DNS_NAMELEN) [KRB5_DNS_LOOKUP]: New macro. + (krb5_locate_srv_conf): Renamed from krb5_locate_kdc; now static; + extra char* argument replaces fixed "kdc" in array of names to + look up in profile. + (krb5_locate_srv_dns) [KRB5_DNS_LOOKUP]: New function; looks up + SRV records, and returns addresses sorted by priority. + (krb5_locate_kdc): New function, calls above routines. + 1999-06-16 Danilo Almeida * ccdefname.c (get_from_registry_indirect, try_dir, get_from_os): diff --git a/src/lib/krb5/os/def_realm.c b/src/lib/krb5/os/def_realm.c index f00c58f47..4d6978395 100644 --- a/src/lib/krb5/os/def_realm.c +++ b/src/lib/krb5/os/def_realm.c @@ -27,6 +27,17 @@ #include "k5-int.h" #include +#ifdef KRB5_DNS_LOOKUP +/* for old Unixes and friends ... */ +#ifndef MAXHOSTNAMELEN +#define MAXHOSTNAMELEN 64 +#endif + +#define MAX_DNS_NAMELEN (15*(MAXHOSTNAMELEN + 1)+1) + +extern int krb5_try_realm_txt_rr(char *,char *, char **); +#endif /* KRB5_DNS_LOOKUP */ + /* * Retrieves the default realm to be used if no user-specified realm is * available. [e.g. to interpret a user-typed principal name with the @@ -64,12 +75,56 @@ krb5_get_default_realm(context, lrealm) retval = profile_get_string(context->profile, "libdefaults", "default_realm", 0, 0, &context->default_realm); - if (context->default_realm == 0) - return(KRB5_CONFIG_NODEFREALM); +#ifdef KRB5_DNS_LOOKUP + if (context->default_realm == 0) { + /* + * Since this didn't appear in our config file, try looking + * it up via DNS. Look for a TXT records of the form: + * + * _kerberos. + * _kerberos. + * _kerberos. + * + */ + char localhost[MAX_DNS_NAMELEN+1]; + char * p; + localhost[0] = localhost[sizeof(localhost)-1] = 0; + gethostname(localhost,MAX_DNS_NAMELEN); + + if ( localhost[0] ) { + p = localhost; + do { + retval = krb5_try_realm_txt_rr("_kerberos", p, + &context->default_realm); + p = strchr(p,'.'); + if (p) + p++; + } while (retval && p && p[0]); + + if (retval) + retval = krb5_try_realm_txt_rr("_kerberos", "", + &context->default_realm); + } else { + retval = krb5_try_realm_txt_rr("_kerberos", "", + &context->default_realm); + } + if (retval) { + return(KRB5_CONFIG_NODEFREALM); + } + } +#endif /* KRB5_DNS_LOOKUP */ } - - realm = context->default_realm; + if (context->default_realm == 0) + return(KRB5_CONFIG_NODEFREALM); + if (context->default_realm[0] == 0) { + free (context->default_realm); + context->default_realm = 0; + return KRB5_CONFIG_NODEFREALM; + } + + realm = context->default_realm; + if (!(*lrealm = cp = malloc((unsigned int) strlen(realm) + 1))) return ENOMEM; strcpy(cp, realm); diff --git a/src/lib/krb5/os/hst_realm.c b/src/lib/krb5/os/hst_realm.c index 0143c343d..13b3a7a3e 100644 --- a/src/lib/krb5/os/hst_realm.c +++ b/src/lib/krb5/os/hst_realm.c @@ -72,11 +72,151 @@ #include #endif +#ifdef KRB5_DNS_LOOKUP +#ifdef WSHELPER +#include +#else /* WSHELPER */ +#include +#include +#include +#include +#endif /* WSHELPER */ +#endif /* KRB5_DNS_LOOKUP */ + /* for old Unixes and friends ... */ #ifndef MAXHOSTNAMELEN #define MAXHOSTNAMELEN 64 #endif +#define MAX_DNS_NAMELEN (15*(MAXHOSTNAMELEN + 1)+1) + +#ifdef KRB5_DNS_LOOKUP +/* + * Try to look up a TXT record pointing to a Kerberos realm + */ + +krb5_error_code +krb5_try_realm_txt_rr(prefix, name, realm) + const char *prefix, *name; + char **realm; +{ + union { + unsigned char bytes[2048]; + HEADER hdr; + } answer; + unsigned char *p; + char host[MAX_DNS_NAMELEN], *h; + int size; + int type, class, numanswers, numqueries, rdlen, len; + + /* + * Form our query, and send it via DNS + */ + + if (name == NULL || name[0] == '\0') { + strcpy(host,prefix); + } else { + if ( strlen(prefix) + strlen(name) + 3 > MAX_DNS_NAMELEN ) + return KRB5_ERR_HOST_REALM_UNKNOWN; + sprintf(host,"%s.%s", prefix, name); + } + /* Realm names don't (normally) end with ".", but if the query + doesn't end with "." and doesn't get an answer as is, the + resolv code will try appending the local domain. Since the + realm names are absolutes, let's stop that. */ + h = host + strlen (host); + if (h > host && h[-1] != '.') + strcpy (h, "."); + + size = res_search(host, C_IN, T_TXT, answer.bytes, sizeof(answer.bytes)); + + if (size < 0) + return KRB5_ERR_HOST_REALM_UNKNOWN; + + p = answer.bytes; + + numqueries = ntohs(answer.hdr.qdcount); + numanswers = ntohs(answer.hdr.ancount); + + p += sizeof(HEADER); + + /* + * We need to skip over the questions before we can get to the answers, + * which means we have to iterate over every query record. We use + * dn_expand to tell us how long each compressed name is. + */ + +#define INCR_CHECK(x, y) x += y; if (x > size + answer.bytes) \ + return KRB5_ERR_HOST_REALM_UNKNOWN +#define CHECK(x, y) if (x + y > size + answer.bytes) \ + return KRB5_ERR_HOST_REALM_UNKNOWN +#define NTOHSP(x, y) x[0] << 8 | x[1]; x += y + + while (numqueries--) { + len = dn_expand(answer.bytes, answer.bytes + size, p, host, + sizeof(host)); + if (len < 0) + return KRB5_ERR_HOST_REALM_UNKNOWN; + INCR_CHECK(p, len + 4); /* Name plus type plus class */ + } + + /* + * We're now pointing at the answer records. Process the first + * TXT record we find. + */ + + while (numanswers--) { + + /* First the name; use dn_expand to get the compressed size */ + len = dn_expand(answer.bytes, answer.bytes + size, p, + host, sizeof(host)); + if (len < 0) + return KRB5_ERR_HOST_REALM_UNKNOWN; + INCR_CHECK(p, len); + + /* Next is the query type */ + CHECK(p, 2); + type = NTOHSP(p,2); + + /* Next is the query class; also skip over 4 byte TTL */ + CHECK(p,6); + class = NTOHSP(p,6); + + /* Record data length - make sure we aren't truncated */ + + CHECK(p,2); + rdlen = NTOHSP(p,2); + + if (p + rdlen > answer.bytes + size) + return KRB5_ERR_HOST_REALM_UNKNOWN; + + /* + * If this is a TXT record, return the string. Note that the + * string has a 1-byte length in the front + */ + /* XXX What about flagging multiple TXT records as an error? */ + + if (class == C_IN && type == T_TXT) { + len = *p++; + if (p + len > answer.bytes + size) + return KRB5_ERR_HOST_REALM_UNKNOWN; + *realm = malloc(len + 1); + if (*realm == NULL) + return ENOMEM; + strncpy(*realm, (char *) p, len); + (*realm)[len] = '\0'; + /* Avoid a common error. */ + if ( (*realm)[len-1] == '.' ) + (*realm)[len-1] = '\0'; + return 0; + } + } + + return KRB5_ERR_HOST_REALM_UNKNOWN; +} +#endif /* KRB5_DNS_LOOKUP */ + + KRB5_DLLIMP krb5_error_code KRB5_CALLCONV krb5_get_host_realm(context, host, realmsp) krb5_context context; @@ -87,15 +227,15 @@ krb5_get_host_realm(context, host, realmsp) char *default_realm, *realm, *cp; krb5_error_code retval; int l; - char local_host[MAXHOSTNAMELEN+1]; + char local_host[MAX_DNS_NAMELEN+1]; if (host) - strncpy(local_host, host, MAXHOSTNAMELEN); + strncpy(local_host, host, MAX_DNS_NAMELEN); else { if (gethostname(local_host, sizeof(local_host)-1) == -1) return SOCKET_ERRNO; } - local_host[sizeof(local_host)-1] = '\0'; + local_host[MAX_DNS_NAMELEN] = '\0'; for (cp = local_host; *cp; cp++) { if (isupper(*cp)) *cp = tolower(*cp); @@ -139,25 +279,56 @@ krb5_get_host_realm(context, host, realmsp) } } +#ifdef KRB5_DNS_LOOKUP if (realm == (char *)NULL) { - if (default_realm != (char *)NULL) { - /* We are defaulting to the realm of the host */ - if (!(cp = (char *)malloc(strlen(default_realm)+1))) - return ENOMEM; - strcpy(cp, default_realm); - realm = cp; - - /* Assume the realm name is upper case */ - for (cp = realm; *cp; cp++) - if (islower(*cp)) - *cp = toupper(*cp); - } else { - /* We are defaulting to the local realm */ - retval = krb5_get_default_realm(context, &realm); - if (retval) { - return retval; - } - } + /* + * Since this didn't appear in our config file, try looking + * it up via DNS. Look for a TXT records of the form: + * + * _kerberos. + * _kerberos. + * _kerberos. + * + */ + cp = local_host; + do { + retval = krb5_try_realm_txt_rr("_kerberos", cp, &realm); + cp = strchr(cp,'.'); + if (cp) + cp++; + } while (retval && cp && cp[0]); + if (retval) + retval = krb5_try_realm_txt_rr("_kerberos", "", &realm); + if (retval && default_realm) { + cp = default_realm; + do { + retval = krb5_try_realm_txt_rr("_kerberos", cp, &realm); + cp = strchr(cp,'.'); + if (cp) + cp++; + } while (retval && cp && cp[0]); + } + } +#endif /* KRB5_DNS_LOOKUP */ + if (realm == (char *)NULL) { + if (default_realm != (char *)NULL) { + /* We are defaulting to the realm of the host */ + if (!(cp = (char *)malloc(strlen(default_realm)+1))) + return ENOMEM; + strcpy(cp, default_realm); + realm = cp; + + /* Assume the realm name is upper case */ + for (cp = realm; *cp; cp++) + if (islower(*cp)) + *cp = toupper(*cp); + } else { + /* We are defaulting to the local realm */ + retval = krb5_get_default_realm(context, &realm); + if (retval) { + return retval; + } + } } if (!(retrealms = (char **)calloc(2, sizeof(*retrealms)))) { if (realm != (char *)NULL) diff --git a/src/lib/krb5/os/locate_kdc.c b/src/lib/krb5/os/locate_kdc.c index 83fd9a3ea..fc19467a9 100644 --- a/src/lib/krb5/os/locate_kdc.c +++ b/src/lib/krb5/os/locate_kdc.c @@ -27,6 +27,26 @@ #define NEED_SOCKETS #include "k5-int.h" #include +#ifdef KRB5_DNS_LOOKUP +#ifdef WSHELPER +#include +#else /* WSHELPER */ +#include +#include +#include +#include +#endif /* WSHELPER */ +#ifndef T_SRV +#define T_SRV 33 +#endif /* T_SRV */ + +/* for old Unixes and friends ... */ +#ifndef MAXHOSTNAMELEN +#define MAXHOSTNAMELEN 64 +#endif + +#define MAX_DNS_NAMELEN (15*(MAXHOSTNAMELEN + 1)+1) +#endif /* KRB5_DNS_LOOKUP */ /* * returns count of number of addresses found @@ -34,16 +54,17 @@ * the master kdc */ -krb5_error_code -krb5_locate_kdc(context, realm, addr_pp, naddrs, master_index, nmasters) +static krb5_error_code +krb5_locate_srv_conf(context, realm, name, addr_pp, naddrs, master_index, nmasters) krb5_context context; const krb5_data *realm; + const char * name; struct sockaddr **addr_pp; int *naddrs; int *master_index; int *nmasters; { - const char *realm_kdc_names[4]; + const char *realm_srv_names[4]; char **masterlist, **hostlist, *host, *port, *cp; krb5_error_code code; int i, j, out, count, ismaster; @@ -65,19 +86,19 @@ krb5_locate_kdc(context, realm, addr_pp, naddrs, master_index, nmasters) masterlist = NULL; - realm_kdc_names[0] = "realms"; - realm_kdc_names[1] = host; - realm_kdc_names[2] = "kdc"; - realm_kdc_names[3] = 0; + realm_srv_names[0] = "realms"; + realm_srv_names[1] = host; + realm_srv_names[2] = name; + realm_srv_names[3] = 0; - code = profile_get_values(context->profile, realm_kdc_names, &hostlist); + code = profile_get_values(context->profile, realm_srv_names, &hostlist); if (code) { - if (code == PROF_NO_SECTION || code == PROF_NO_RELATION) - code = KRB5_REALM_UNKNOWN; - krb5_xfree(host); - return code; - } + if (code == PROF_NO_SECTION || code == PROF_NO_RELATION) + code = KRB5_REALM_UNKNOWN; + krb5_xfree(host); + return code; + } #ifdef HAVE_NETINET_IN_H if ((sp = getservbyname(KDC_PORTNAME, "udp"))) @@ -102,12 +123,12 @@ krb5_locate_kdc(context, realm, addr_pp, naddrs, master_index, nmasters) *master_index = 0; *nmasters = 0; - realm_kdc_names[0] = "realms"; - realm_kdc_names[1] = host; - realm_kdc_names[2] = "admin_server"; - realm_kdc_names[3] = 0; + realm_srv_names[0] = "realms"; + realm_srv_names[1] = host; + realm_srv_names[2] = "admin_server"; + realm_srv_names[3] = 0; - code = profile_get_values(context->profile, realm_kdc_names, + code = profile_get_values(context->profile, realm_srv_names, &masterlist); krb5_xfree(host); @@ -236,3 +257,371 @@ krb5_locate_kdc(context, realm, addr_pp, naddrs, master_index, nmasters) *naddrs = out; return 0; } + +#ifdef KRB5_DNS_LOOKUP + +/* + * Lookup a KDC via DNS SRV records + */ + +static krb5_error_code +krb5_locate_srv_dns(realm, service, protocol, addr_pp, naddrs) + const krb5_data *realm; + const char *service; + const char *protocol; + struct sockaddr **addr_pp; + int *naddrs; +{ + krb5_error_code code; + int out, j, count; + union { + unsigned char bytes[2048]; + HEADER hdr; + } answer; + unsigned char *p=NULL; + char host[MAX_DNS_NAMELEN]; + struct sockaddr *addr = NULL; + struct sockaddr_in *sin = NULL; + struct hostent *hp = NULL; + int type, class; + int status, priority, weight, size, len, numanswers, numqueries, rdlen; + unsigned short port; + const int hdrsize = sizeof(HEADER); + struct srv_dns_entry { + struct srv_dns_entry *next; + int priority; + int weight; + unsigned short port; + char *host; + }; + + struct srv_dns_entry *head = NULL; + struct srv_dns_entry *srv = NULL, *entry = NULL; + + out = 0; + addr = (struct sockaddr *) malloc(sizeof(struct sockaddr)); + if (addr == NULL) + return ENOMEM; + + count = 1; + + /* + * First off, build a query of the form: + * + * service.protocol.realm + * + * which will most likely be something like: + * + * _kerberos._udp.REALM + * + */ + + if ( strlen(service) + strlen(protocol) + realm->length + 5 + > MAX_DNS_NAMELEN ) + goto out; + sprintf(host, "%s.%s.%.*s", service, protocol, realm->length, + realm->data); + + size = res_search(host, C_IN, T_SRV, answer.bytes, sizeof(answer.bytes)); + + if (size < hdrsize) + goto out; + + /* + * We got an answer! First off, parse the header and figure out how + * many answers we got back. + */ + + p = answer.bytes; + + numqueries = ntohs(answer.hdr.qdcount); + numanswers = ntohs(answer.hdr.ancount); + + p += sizeof(HEADER); + + /* + * We need to skip over all of the questions, so we have to iterate + * over every query record. dn_expand() is able to tell us the size + * of compress DNS names, so we use it. + */ + +#define INCR_CHECK(x,y) x += y; if (x > size + answer.bytes) goto out +#define CHECK(x,y) if (x + y > size + answer.bytes) goto out +#define NTOHSP(x,y) x[0] << 8 | x[1]; x += y + + while (numqueries--) { + len = dn_expand(answer.bytes, answer.bytes + size, p, host, sizeof(host)); + if (len < 0) + goto out; + INCR_CHECK(p, len + 4); + } + + /* + * We're now pointing at the answer records. Only process them if + * they're actually T_SRV records (they might be CNAME records, + * for instance). + * + * But in a DNS reply, if you get a CNAME you always get the associated + * "real" RR for that CNAME. RFC 1034, 3.6.2: + * + * CNAME RRs cause special action in DNS software. When a name server + * fails to find a desired RR in the resource set associated with the + * domain name, it checks to see if the resource set consists of a CNAME + * record with a matching class. If so, the name server includes the CNAME + * record in the response and restarts the query at the domain name + * specified in the data field of the CNAME record. The one exception to + * this rule is that queries which match the CNAME type are not restarted. + * + * In other words, CNAMEs do not need to be expanded by the client. + */ + + while (numanswers--) { + + /* First is the name; use dn_expand to get the compressed size */ + len = dn_expand(answer.bytes, answer.bytes + size, p, host, sizeof(host)); + if (len < 0) + goto out; + INCR_CHECK(p, len); + + /* Next is the query type */ + CHECK(p, 2); + type = NTOHSP(p,2); + + /* Next is the query class; also skip over 4 byte TTL */ + CHECK(p, 6); + class = NTOHSP(p,6); + + /* Record data length */ + + CHECK(p,2); + rdlen = NTOHSP(p,2); + + /* + * If this is an SRV record, process it. Record format is: + * + * Priority + * Weight + * Port + * Server name + */ + + if (class == C_IN && type == T_SRV) { + CHECK(p,2); + priority = NTOHSP(p,2); + CHECK(p, 2); + weight = NTOHSP(p,2); + CHECK(p, 2); + port = NTOHSP(p,2); + len = dn_expand(answer.bytes, answer.bytes + size, p, host, sizeof(host)); + if (len < 0) + goto out; + INCR_CHECK(p, len); + + /* + * We got everything! Insert it into our list, but make sure + * it's in the right order. Right now we don't do anything + * with the weight field + */ + + srv = (struct srv_dns_entry *) malloc(sizeof(struct srv_dns_entry)); + if (srv == NULL) + goto out; + + srv->priority = priority; + srv->weight = weight; + srv->port = port; + srv->host = strdup(host); + + if (head == NULL || head->priority > srv->priority) { + srv->next = head; + head = srv; + } else + /* + * This is confusing. Only insert an entry into this + * spot if: + * The next person has a higher priority (lower priorities + * are preferred). + * Or + * There is no next entry (we're at the end) + */ + for (entry = head; entry != NULL; entry = entry->next) + if ((entry->next && + entry->next->priority > srv->priority) || + entry->next == NULL) { + srv->next = entry->next; + entry->next = srv; + break; + } + } else + INCR_CHECK(p, rdlen); + } + + /* + * Okay! Now we've got a linked list of entries sorted by + * priority. Start looking up A records and returning + * addresses. + */ + + if (head == NULL) + goto out; + + for (entry = head; entry != NULL; entry = entry->next) { + hp = gethostbyname(entry->host); + if (hp != 0) { + switch (hp->h_addrtype) { +#ifdef HAVE_NETINET_IN_H + case AF_INET: + for (j=0; hp->h_addr_list[j]; j++) { + sin = (struct sockaddr_in *) &addr[out++]; + memset ((char *) sin, 0, sizeof (struct sockaddr)); + sin->sin_family = hp->h_addrtype; + sin->sin_port = htons(entry->port); + memcpy((char *) &sin->sin_addr, + (char *) hp->h_addr_list[j], + sizeof(struct in_addr)); + if (out + 1 >= count) { + count += 5; + addr = (struct sockaddr *) + realloc((char *) addr, + sizeof(struct sockaddr) * count); + if (!addr) + goto out; + } + } + break; +#endif /* HAVE_NETINET_IN_H */ + default: + break; + } + } + } + + for (entry = head; entry != NULL; ) { + free(entry->host); + entry->host = NULL; + srv = entry; + entry = entry->next; + free(srv); + srv = NULL; + } + + out: + if (srv) + free(srv); + + if (out == 0) { /* No good servers */ + if (addr) + free(addr); + return KRB5_REALM_CANT_RESOLVE; + } + + *addr_pp = addr; + *naddrs = out; + return 0; +} +#endif /* KRB5_DNS_LOOKUP */ + +/* + * Wrapper function for the two backends + */ + +krb5_error_code +krb5_locate_kdc(context, realm, addr_pp, naddrs, master_index, nmasters) + krb5_context context; + const krb5_data *realm; + struct sockaddr **addr_pp; + int *naddrs; + int *master_index; + int *nmasters; +{ + krb5_error_code code; +#ifdef KRB5_DNS_LOOKUP + struct sockaddr *admin_addr_p, *kdc_addr_p; + int nadmin_addrs, nkdc_addrs; + int i,j; +#endif /* KRB5_DNS_LOOKUP */ + + /* + * We always try the local file first + */ + + code = krb5_locate_srv_conf(context, realm, "kdc", addr_pp, naddrs, + master_index, nmasters); + +#ifdef KRB5_DNS_LOOKUP + if (code) { + code = krb5_locate_srv_dns(realm, "_kerberos", "_udp", + addr_pp, naddrs); + if ( master_index && nmasters ) { + + code = krb5_locate_srv_dns(realm, "_kadmin", "_tcp", + &admin_addr_p, &nadmin_addrs); + if ( code ) { + free(*addr_pp); + *addr_pp = NULL; + *naddrs = 0; + return(code); + } + + kdc_addr_p = *addr_pp; + nkdc_addrs = *naddrs; + + *naddrs = 0; + *addr_pp = (struct sockaddr *) malloc(sizeof(*kdc_addr_p)); + if ( *addr_pp == NULL ) { + free(kdc_addr_p); + free(admin_addr_p); + return ENOMEM; + } + + for ( i=0; i