jech / dht Goto Github PK

The if(oldest->done) check that was added in recent commit 71d4372 appears to be redundant, as oldest->done is necessarily set. The loop at the beginning of the function ensures it:

    sr = searches;
    while(sr) {
        if(sr->done &&
           (oldest == NULL || oldest->step_time > sr->step_time))
            oldest = sr;
        sr = sr->next;
    }

However, this changes does make the point that it's fine for the new_search function to return a "done" slot. But isn't it supposed to be taken care of earlier in the function by the following lines ?

    /* The oldest slot is expired. */
    if(oldest && oldest->step_time < now.tv_sec - DHT_SEARCH_EXPIRE_TIME)
        return oldest;

Or maybe I'm wrong because we consider it's fine to return a "done" search that's not yet expired ? If that's the case, it seems that the observation I was making in PR #45 was incorrect and, we could revert the code back to before this change.

Also, you seem to have forgotten the possibility that oldest is NULL at that point in the function. It would be the case if no search is currently marked as "done".

Tracking when a search completes is somewhat difficult at the moment. If the user allocates memory for a search, calls dht_search(), and then deallocates when DHT_EVENT_SEARCH_DONE arrives, memory can leak. The user can try to keep track of in-progress searches, and also its own timeout values, but this is is extra effort and slightly inaccurate.

There are a few small things I think could be improved about the API which should be backwards compatible:

• if dht_search finds an existing struct search, it could return a different value (2?) so the caller knows not to expect an additional DHT_EVENT_SEARCH_DONE event
• when a struct search expires, callback with DHT_EVENT_SEARCH_DONE(6) before freeing

I'd be happy to submit a pull request if these are welcome changes.

From other implementations (libbtdht, KTorrent), I understand bootstrapping is usually done like this:

• add bootstrap nodes with fake ids as far away as possible from one's own id
• send find_node for slightly modified own id to bootstrap nodes
• bootstrap is considered complete when a certain routing table depth (*) is reached

Here's how libbtdht does it:
https://github.com/bittorrent/libbtdht/blob/200b8adf83edeb84f1c81fb82de7e5b8624a5fa4/src/DhtImpl.cpp#L2673
https://github.com/bittorrent/libbtdht/blob/200b8adf83edeb84f1c81fb82de7e5b8624a5fa4/src/DhtImpl.cpp#L1263

(*) libbtdht refers to this as 'span', but I currently fail to understand how it is being calculated.

Would you care to add a similar mechanism?

dht.c 1668

if(s >= 0) {
    buckets = calloc(sizeof(struct bucket), 1);
    if(buckets == NULL)
        return -1;
    buckets->af = AF_INET;

    rc = set_nonblocking(s, 1);
    if(rc < 0)
        goto fail;
}

if(s6 >= 0) {
    buckets6 = calloc(sizeof(struct bucket), 1);
    if(buckets6 == NULL)
        return -1;
    buckets6->af = AF_INET6;

    rc = set_nonblocking(s6, 1);
    if(rc < 0)
        goto fail;
}

...

 fail:
    free(buckets);
    buckets = NULL;
    free(buckets6);
    buckets6 = NULL;
    return -1;

what happens if _set_nonblocking(s, 1)_ returned an error
before we might _buckets6 = calloc_ (which comes after)
_fail:_ free(buckets6) ?

Or maybe the opposite
no v4 socket at all and _set_nonblocking(s6, 1)_ returns error
_fail:_ free(buckets) ?

maybe I'm not seeing this right...

Messages should include a "v" key with a 4-byte identifier value that contains the DHT node's 2-byte client identifier and 2-byte version identifier. This helps immensely in tracking down bugs in other DHT implementations, as you can get an idea of which implementation you are or aren't looking for.

See BEP 5 for details about the client version string.

regards code of buffer_closest_nodes, a trivial way is to scan the bucket and its adjacent buckets and find the 8 closest node , what's your consideration

If a message includes the "implied_port" argument, the message parser finds the "port" portion of the "implied_port" argument key and uses its value as the port, which is always 0 or 1.

See BEP 5 for proper handling of the "implied_port" argument.

It's a really good implementation for DHT.

But I am a little confused with the algorithm for finding nodes. I think the most wonderful part of
Kademlia DHT is that we can do a recursive lookup, and each step we can make it half-more-closer to the target(aha, I have named it half-way-iteration-efficent.). And the most important data struct is how it deals with buckets, or route table.

As the described in Ethereum P2P Node Discovery.

Simple to say, It make use of an N size buckets with the i bucket storing the nodes have i common prefix as MyId.

But, as codes below, It uses a bucket link and iterate the 3 nearby buckets and pick the k nearest nodes. I have not figured out how It can make a half-way-iteration-efficent? Or if there something wrong understand to me, please sort me out, will be thankful.

b = find_bucket(id, AF_INET);
if(b) {
    numnodes = buffer_closest_nodes(nodes, numnodes, id, b);
     if(b->next)
         numnodes = buffer_closest_nodes(nodes, numnodes, id, b->next);
     b = previous_bucket(b);
     if(b)
        numnodes = buffer_closest_nodes(nodes, numnodes, id, b);
}

Would be nice if the library have support to store arbitrary values,
so other decentralized application could integrate with the Bittorrent DHT more easily.

Have found this was asked before (in issue #9 ).
But, now there is a BEP related (http://bittorrent.org/beps/bep_0044.html).

I think other libraries and programs (like libtorrent) has implemented it.
But i have not found a DHT specific library (in c/c++) with it.

Thanks

Bug: struct bucket.time is defined as int - should be time_t

I've been monitoring activity on this project for a while and many pull requests and issues have been left unanswered for a while.

BEP 5 has been updated to document the long standing de-facto standard of including a version string in RPC messages. This is an important feature for identifying implementations which may be lacking features or misbehaving. The relevant section of BEP5:

A key v should be included in every message with a client version string. The string should be a two character client identifier registered in BEP 20 followed by a two character version identifier.

By convention the version string identifies the DHT implementation rather than the client application. Thus this library should have it's own client identifier which it uses to populate the version string. Ideally it would always use this string regardless of what the client application's identifier is.

I didn't see a method for storing/publishing values. Is this correct?

How difficult would it be to implement such a function. I am willing to do it if it's not to complicated.

BEP-14 adds support for local peer discovery, which seems to be a nice complement for speeding up both searches and peer discovery.

I came across this working on the Debian integration of transmission. There's the option of using a system DHT library instead of bundling it, but if I see correctly, dht can't build as a library yet. I don't know why not, given that dht is so useful.

I could create a PR that add that, if you'd like.

The first function int Bootstrapping section is dht_ping_node, not dht_ping.