From 384545ce291041b819661bf6d66b00e4c8ee88fd Mon Sep 17 00:00:00 2001 From: Leandro Lucarella Date: Thu, 22 Jun 2006 20:37:14 +0000 Subject: [PATCH 1/1] =?utf8?q?Primera=20aproximaci=C3=B3n=20al=20cache=20y?= =?utf8?q?=20a=20la=20resoluci=C3=B3n=20de=20nombres.?= MIME-Version: 1.0 Content-Type: text/plain; charset=utf8 Content-Transfer-Encoding: 8bit --- practicas/pipi/src/Makefile | 11 +- practicas/pipi/src/nameserver.cpp | 205 ++++++++++++++++-- practicas/pipi/src/nameserver.h | 34 ++- .../pipi/src/test_nameserver_resolvnext.cpp | 23 ++ 4 files changed, 250 insertions(+), 23 deletions(-) create mode 100644 practicas/pipi/src/test_nameserver_resolvnext.cpp diff --git a/practicas/pipi/src/Makefile b/practicas/pipi/src/Makefile index bbd1d67..69008bc 100644 --- a/practicas/pipi/src/Makefile +++ b/practicas/pipi/src/Makefile @@ -32,7 +32,8 @@ CC=g++ # Programas targets=ip tests=test_send test_recv test_ipaddr test_ipin test_ipout test_devtcp \ - test_poll test_resolvprotos test_resolvprotoc test_nameserver_file + test_poll test_resolvprotos test_resolvprotoc test_nameserver_file \ + test_nameserver_resolvnext # Fuentes fuentes ?= $(wildcard *.cpp) $(wildcard *.c) @@ -67,6 +68,8 @@ test_resolvprotoc: test_resolvprotoc.o libtcp.o ipaddr.o resolvproto.o test_nameserver_file: test_nameserver_file.o ipaddr.o nameserver.o +test_nameserver_resolvnext: test_nameserver_resolvnext.o ipaddr.o nameserver.o + ip: ip.o ipout.o ipin.o ipaddr.o ipheader.o devque.o devtcp.o routetable.o libtcp.o depend: @@ -286,6 +289,12 @@ test_nameserver_file.o: nameserver.h ipaddr.h /usr/include/stdint.h test_nameserver_file.o: /usr/include/features.h /usr/include/sys/cdefs.h test_nameserver_file.o: /usr/include/gnu/stubs.h /usr/include/bits/wchar.h test_nameserver_file.o: /usr/include/bits/wordsize.h +test_nameserver_resolvnext.o: nameserver.h ipaddr.h /usr/include/stdint.h +test_nameserver_resolvnext.o: /usr/include/features.h +test_nameserver_resolvnext.o: /usr/include/sys/cdefs.h +test_nameserver_resolvnext.o: /usr/include/gnu/stubs.h +test_nameserver_resolvnext.o: /usr/include/bits/wchar.h +test_nameserver_resolvnext.o: /usr/include/bits/wordsize.h test_recv.o: devque.h dev.h /usr/include/unistd.h /usr/include/features.h test_recv.o: /usr/include/sys/cdefs.h /usr/include/gnu/stubs.h test_recv.o: /usr/include/bits/posix_opt.h /usr/include/bits/types.h diff --git a/practicas/pipi/src/nameserver.cpp b/practicas/pipi/src/nameserver.cpp index 2814427..45ec63d 100644 --- a/practicas/pipi/src/nameserver.cpp +++ b/practicas/pipi/src/nameserver.cpp @@ -2,21 +2,23 @@ #include #include #include -#ifdef DEBUG2 +#include +#include +#ifdef DEBUG #include #endif -static void parsename(const std::string& s, NameServer::name_t& name) +#define DEBUG_RESOLV + +NameServer::Name::Name(const std::string& s) { std::istringstream iss(s); std::string tok; while (std::getline(iss, tok, '.')) - { - name.push_back(tok); - } + push_back(tok); } -static std::ostream& operator<< (std::ostream& os, const NameServer::name_t& name) +std::ostream& operator<< (std::ostream& os, const NameServer::Name& name) { if (name.empty()) return os; @@ -25,6 +27,13 @@ static std::ostream& operator<< (std::ostream& os, const NameServer::name_t& nam return os << name.back(); } +NameServer::Name::operator std::string () +{ + std::stringstream ss; + ss << *this; + return ss.str(); +} + /// Parsea una zona static std::istream& parsezone(std::istream& is, NameServer::Zone& z) throw (std::runtime_error) @@ -37,8 +46,8 @@ static std::istream& parsezone(std::istream& is, NameServer::Zone& z) std::istringstream iss(line); if (!(iss >> sname >> z.ttl >> ip)) throw std::runtime_error("Error al parsear"); - parsename(sname, z.name); -#ifdef DEBUG2 + z.name = sname; +#ifdef DEBUG_PARSER std::cerr << "parsezone: IP = " << ip << "\n\n"; #endif z.parent = IPAddr(ip); @@ -52,13 +61,13 @@ static std::istream& parsezone(std::istream& is, NameServer::Zone& z) if (!(iss >> key >> type >> ip)) throw std::runtime_error("Error al parsear"); typedef NameServer::Record Rec; -#ifdef DEBUG2 +#ifdef DEBUG_PARSER std::cerr << "parsezone: IP = " << ip << "\n\n"; #endif Rec r((type == "NS") ? Rec::NS : Rec::A, IPAddr(ip)); z.records.insert(NameServer::Zone::records_t::value_type(key, r)); } -#ifdef DEBUG2 +#ifdef DEBUG_PARSER std::cerr << "parsezone: " << z << "\n\n"; #endif return is; @@ -66,9 +75,8 @@ static std::istream& parsezone(std::istream& is, NameServer::Zone& z) /// Constructor NameServer::Zone::Zone(std::string sname, size_t ttl, const IPAddr& parent): - ttl(ttl), parent(parent) + name(sname), ttl(ttl), parent(parent) { - parsename(sname, name); } /// Constructor @@ -96,19 +104,172 @@ NameServer::NameServer(std::istream& is) { zones.push_back(z); z.clear(); -#ifdef DEBUG2 +#ifdef DEBUG_PARSER std::cerr << "NameServer: " << z << "\n\n"; #endif } } -std::ostream& operator<< (std::ostream& os, const NameServer::Record& r) +/// Devuelve la parte izquierda de n, si la parte derecha coincide exactamente +/// con m, si no devuelve un vector vacío. +/// Elemplo: name_split("mi.domi.nio", "domi.nio") == ["mi"] +/// name_split("dos.mi.domi.nio", "domi.nio") == ["dos", "mi"] +/// name_split("domi.nio", "domi.nio") == [] +/// name_split("papeli.nio", "domi.nio") == [] +static NameServer::Name +name_split(NameServer::Name n, NameServer::Name m) +{ + NameServer::Name r; + std::reverse(n.begin(), n.end()); + std::reverse(m.begin(), m.end()); + // Si m es más grande o igual que n, no hay nada que hacer + if (n.size() <= m.size()) + return r; + // Si no coincide la parte derecha, no hay nada que hacer + NameServer::Name::size_type i; + for (i = 0; i < m.size(); ++i) + if (n[i] != m[i]) + return r; + // Si era todo igual y sobran cosas, devolvemos lo que "sobra" + while (i < n.size()) + r.push_back(n[i++]); + std::reverse(r.begin(), r.end()); +#ifdef DEBUG_NAME + std::cerr << "name_split(" << n << ", " << m << ") -> " << r << "\n"; +#endif + return r; +} + +/// Devuelve -1 si es un nombre "hijo" (la parte derecha de n está contenida +/// completamente en m, pero m y n no son iguales), 0 si m == n y 1 si es +/// "padre" (m no coincide con la parte derecha de n). +/// Elemplo: namecmp("mi.domi.nio", "domi.nio") == -1 +/// namecmp("otra.cosa", "domi.nio") == 1 +/// namecmp("papeli.nio", "domi.nio") == 1 +/// namecmp("domi.nio", "domi.nio") == 0 +/*enum name_cmp_t +{ + NC_DIRECT_CHILD, ///> Hijo directo, es decir, está en la zona m + NC_CHILD, ///> Hijo indirecto, está en una zona que cuelga de m + NC_EQUAL, ///> Es el host de la zona m + NC_DIRECT_PARENT, ///> Padre directo, es decir, coincide en parte con m + NC_PARENT ///> Padre indirecto, es completamente distinto a m +};*/ +#if 0 +static int name_cmp(const NameServer::Name& n, const NameServer::Name& m) +{ + // Si m es más grande que n, seguro es padre + if (n.size() < m.size()) + return 1; + // Si no coincide la parte derecha, seguro es padre + NameServer::Name::size_type i; + for (i = m.size(); i > 0; --i) + if (n[i-1] != m[i-1]) + return 1; + // Si era todo igual y sobran cosas, es hijo + if (i) + return -1; + // Si no, son iguales. + return 0; +} +#endif + +struct search_zone: std::unary_function< NameServer::Zone, bool > +{ + bool local; + NameServer::CacheRecord crecord; + const NameServer::Name& name; + search_zone(const NameServer::Name& n): local(false), name(n) {} + bool operator() (const NameServer::Zone& z) + { + bool found = false; + NameServer::Name local_part = name_split(name, z.name); + if (!local_part.empty()) // Está en esta zona + { + local = true; + std::string n = local_part.back(); // Obtengo última parte + // busco + typedef NameServer::Zone::records_t::const_iterator itt; + std::pair p = z.records.equal_range(n); + for (; p.first != p.second; ++p.first) + { + const NameServer::Record& r = (*p.first).second; + // Tiene que buscar solo A porque era un nombre + if ((local_part.size() == 1) && (r.type != NameServer::Record::A)) + continue; + // Tiene que seguir para abajo, solo busca NS + if ((local_part.size() > 1) && r.type != NameServer::Record::NS) + continue; + found = true; + crecord.ttl = z.ttl; + crecord.records.push_back(r); + } + } + return found; + } +}; + +void NameServer::resolv_next(const Name& n) +{ +#ifdef DEBUG_RESOLV + std::cerr<< "resolv_next -> tratando de resolver: " << n << "\n"; +#endif + search_zone zs(n); + bool found; + for (zones_t::const_iterator i = zones.begin(); i!= zones.end(); ++i) + if ((found = zs(*i))) + break; + if (found) + { + // TODO mandar resultados? +#ifdef DEBUG_RESOLV + std::cerr<< "resolv_next found (local/hijo): " << zs.crecord << "\n"; +#endif + return; + } + if (zs.local) + { + // TODO mandar NOT FOUND +#ifdef DEBUG_RESOLV + std::cerr<< "resolv_next NOT FOUND (es local pero no existe)\n"; +#endif + return; + } + cache_t::const_iterator i = cache.find(n); + if (i != cache.end()) + { + // TODO mandar resultados? +#ifdef DEBUG_RESOLV + std::cerr<< "resolv_next found (en cache): " << i->second << "\n"; +#endif + return; + } + // TODO enviar nameserver padre, si no hay padre, mandar NOT FOUND + if (zones.size()) + { +#ifdef DEBUG_RESOLV + std::cerr << "resolv_next found (al padre): " << zones.front().parent + << "\n"; + return; +#endif + } + // TODO enviar NOT FOUND +#ifdef DEBUG_RESOLV + std::cerr<< "resolv_next NOT FOUND (no hay padre)\n"; +#endif +} + +std::ostream& operator<< (std::ostream& os, const NameServer::Record::type_t& t) { - if (r.type == NameServer::Record::NS) - os << "NS "; + if (t == NameServer::Record::NS) + return os << "NS"; else - os << "A "; - return os << r.ip; + return os << "A"; +} + +std::ostream& operator<< (std::ostream& os, const NameServer::Record& r) +{ + return os << r.type << " " << r.ip; } std::ostream& operator<< (std::ostream& os, @@ -125,6 +286,14 @@ std::ostream& operator<< (std::ostream& os, const NameServer::Zone& z) return os; } +std::ostream& operator<< (std::ostream& os, const NameServer::CacheRecord& cr) +{ + os << "CacheRecord(ttl=" << cr.ttl << ", records="; + std::copy(cr.records.begin(), cr.records.end(), + std::ostream_iterator< NameServer::Record >(os, ",")); + return os << ")"; +} + std::ostream& operator<< (std::ostream& os, const NameServer& ns) { os << "NameServer: zones[" << ns.zones.size() << "] (\n\n"; diff --git a/practicas/pipi/src/nameserver.h b/practicas/pipi/src/nameserver.h index 686fb52..d0fa98d 100644 --- a/practicas/pipi/src/nameserver.h +++ b/practicas/pipi/src/nameserver.h @@ -15,7 +15,13 @@ struct NameServer { /// Nombre de un dominio dividido en tokens - typedef std::vector< std::string > name_t; + struct Name: std::vector< std::string > + { + /// Constructor + Name() {} + Name(const std::string& name); + operator std::string (); + }; /// Registro de una zona struct Record @@ -33,7 +39,7 @@ struct NameServer struct Zone { /// Nombre - name_t name; + Name name; /// Time to live size_t ttl; /// Nodo padre @@ -49,21 +55,41 @@ struct NameServer void clear(); }; - //TODO cache de _records_ (no zonas) - /// Zonas para las que este servidor de nombres es autoridad typedef std::vector< Zone > zones_t; zones_t zones; + /// Cache de un registro + struct CacheRecord + { + /// Time to live + size_t ttl; + /// Dirección IP del registro + typedef std::vector< Record > records_t; + records_t records; + /// Constructor + CacheRecord(): ttl(0) {} + CacheRecord(size_t ttl, const records_t& records): + ttl(ttl), records(records) {} + }; + + /// Cache de records + typedef std::map< Name, CacheRecord > cache_t; + cache_t cache; + /// Constructor NameServer(std::istream& is) throw (std::runtime_error); + /// Resuelve un nombre de forma no recursiva + void resolv_next(const Name& n); }; /// Impresión (para debug) std::ostream& operator<< (std::ostream& os, const NameServer& ns); +std::ostream& operator<< (std::ostream& os, const NameServer::Name& name); std::ostream& operator<< (std::ostream& os, const NameServer::Record& r); std::ostream& operator<< (std::ostream& os, const NameServer::Zone& z); +std::ostream& operator<< (std::ostream& os, const NameServer::CacheRecord& cr); #endif // _NAMESERVER_H_ diff --git a/practicas/pipi/src/test_nameserver_resolvnext.cpp b/practicas/pipi/src/test_nameserver_resolvnext.cpp new file mode 100644 index 0000000..d510483 --- /dev/null +++ b/practicas/pipi/src/test_nameserver_resolvnext.cpp @@ -0,0 +1,23 @@ + +#include "nameserver.h" +#include +#include +#include +#include + +int main(int argc, char* argv[]) +{ + typedef NameServer::Name N; + std::ifstream ifs("test_nameserver_zones.txt"); + NameServer ns(ifs); + std::cout << ns << "\n"; + ns.resolv_next(N("tito.mi.super.nombre")); + ns.resolv_next(N("juan.mi.super.nombre")); + ns.resolv_next(N("pepe.otro.mi.super.nombre")); + ns.resolv_next(N("pepe.mas.mi.super.nombre")); + ns.resolv_next(N("super.nombre")); + ns.resolv_next(N("nada.que.ver")); + return 0; +} + +// vim: set et sw=4 sts=4 : -- 2.43.0