piececache.c

来自「elinks下lynx是最重要的二个文本浏览器, 在linux下非常实用, el」· C语言 代码 · 共 1,360 行 · 第 1/3 页

/* BitTorrent piece cache */

#ifdef HAVE_CONFIG_H
#include "config.h"
#endif

#include <errno.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/types.h>
#include <sys/stat.h> /* OS/2 needs this after sys/types.h */
#ifdef HAVE_FCNTL_H
#include <fcntl.h> /* OS/2 needs this after sys/types.h */
#endif
#ifdef HAVE_UNISTD_H
#include <unistd.h>
#endif

#include "elinks.h"

#include "cache/cache.h"
#include "main/select.h"
#include "network/connection.h"
#include "osdep/osdep.h"
#include "protocol/bittorrent/bencoding.h"
#include "protocol/bittorrent/common.h"
#include "protocol/bittorrent/connection.h"
#include "protocol/bittorrent/dialogs.h"
#include "protocol/bittorrent/peerwire.h"
#include "protocol/bittorrent/piececache.h"
#include "protocol/bittorrent/tracker.h"
#include "util/bitfield.h"
#include "util/error.h"
#include "util/file.h"
#include "util/lists.h"
#include "util/memory.h"
#include "util/string.h"


/* Used as a 'not defined' value for piece indexes. */
#define BITTORRENT_PIECE_UNDEF		UINT_MAX

/* Used as a 'not interesting' value for piece rarities. */
#define BITTORRENT_PIECE_RARITY_UNDEF	USHRT_MAX

/* A shorthand to reduce long lines. */
#define find_local_bittorrent_peer_request(peer, request) \
	get_bittorrent_peer_request(&(peer)->local, (request)->piece, \
				    (request)->offset, (request)->length)

static inline void
set_bittorrent_piece_cache_remaining(struct bittorrent_piece_cache *cache,
				     uint32_t piece, int remaining)
{
	cache->entries[piece].remaining = remaining > 0 ? 1 : 0;
	cache->remaining_pieces += remaining;
	cache->loading_pieces   += -remaining;
}

static inline void
set_bittorrent_piece_cache_completed(struct bittorrent_piece_cache *cache,
				     uint32_t piece)
{
	cache->entries[piece].completed = 1;
	cache->entries[piece].remaining = 0;
	cache->loading_pieces--;
	cache->completed_pieces++;
	set_bitfield_bit(cache->bitfield, piece);
}

static void
handle_bittorrent_mode_changes(struct bittorrent_connection *bittorrent)
{
	struct bittorrent_piece_cache *cache = bittorrent->cache;

	if (cache->completed_pieces == bittorrent->meta.pieces
	    || (cache->partial && cache->partial_pieces == cache->completed_pieces)) {
		struct bittorrent_peer_connection *peer;

		bittorrent->mode = BITTORRENT_MODE_SEEDER;

		/* Loose all interest ... */
		foreach (peer, bittorrent->peers)
			set_bittorrent_peer_not_interested(peer);

		if (cache->notify_complete)
			notify_bittorrent_download_complete(bittorrent);

		if (!cache->partial) {
			bittorrent->tracker.event = BITTORRENT_EVENT_COMPLETED;
			send_bittorrent_tracker_request(bittorrent->conn);
		}

	} else if (bittorrent->mode == BITTORRENT_MODE_PIECELESS) {
		int cutoff;

		cutoff = get_opt_int("protocol.bittorrent.rarest_first_cutoff");
		if (cache->completed_pieces >= cutoff)
			bittorrent->mode = BITTORRENT_MODE_NORMAL;
	}
}


/* ************************************************************************** */
/* Piece cache free list management: */
/* ************************************************************************** */

/* Search the free list for a request that is available from the peer. */
static struct bittorrent_peer_request *
find_bittorrent_free_list_peer_request(struct bittorrent_piece_cache *cache,
				       struct bittorrent_peer_connection *peer)
{
	struct bittorrent_peer_request *request;
	uint32_t piece = BITTORRENT_PIECE_UNDEF;

	foreach (request, cache->free_list) {
		/* Skip consecutive request for pieces that the peer does not
		 * have. */
		if (request->piece == piece)
			continue;

		piece = request->piece;

		/* Got piece? */
		if (!test_bitfield_bit(peer->bitfield, request->piece))
			continue;

		del_from_list(request);
		return request;
	}

	return NULL;
}

static inline int
randomize(size_t scale)
{
	double random = (double) rand() / RAND_MAX;
	int index = random * (scale - 1);

	return index;
}

/* Pseudo-randomly select a piece that is available from the peer. */
static uint32_t
find_random_in_bittorrent_piece_cache(struct bittorrent_piece_cache *cache,
				      struct bittorrent_peer_connection *peer)
{
	uint32_t pieces[] = {
		BITTORRENT_PIECE_UNDEF, BITTORRENT_PIECE_UNDEF,
		BITTORRENT_PIECE_UNDEF, BITTORRENT_PIECE_UNDEF,
		BITTORRENT_PIECE_UNDEF, BITTORRENT_PIECE_UNDEF,
		BITTORRENT_PIECE_UNDEF, BITTORRENT_PIECE_UNDEF,
		BITTORRENT_PIECE_UNDEF, BITTORRENT_PIECE_UNDEF,
		BITTORRENT_PIECE_UNDEF, BITTORRENT_PIECE_UNDEF,
		BITTORRENT_PIECE_UNDEF, BITTORRENT_PIECE_UNDEF,
		BITTORRENT_PIECE_UNDEF, BITTORRENT_PIECE_UNDEF,
		BITTORRENT_PIECE_UNDEF, BITTORRENT_PIECE_UNDEF,
		BITTORRENT_PIECE_UNDEF, BITTORRENT_PIECE_UNDEF,
	};
	int places = sizeof_array(pieces);
	uint32_t piece;

	assert(peer->bitfield->bitsize == peer->bittorrent->meta.pieces);

	srand(time(NULL));

	foreachback_bitfield_set (piece, peer->bitfield) {
		assertm(cache->entries[piece].rarity,
			"Piece cache out of sync");

		if (!cache->entries[piece].remaining)
			continue;

		/* A little stupid, but in the first few iterations it tries to
		 * equally fill out the array with available pieces to quickly
		 * get a reasonable variety of pieces to choose from. It then
		 * changes to randomly position available pieces in the array.
		 * Assuming a piece table size of 10 it would behave in the
		 * following way:
		 *
		 *		  0 1 2 3 4 5 6 7 8 9
		 *	-----------------------------
		 *	 1. found * * * * * * * * * *
		 *	 2. found *   *   *   *   *
		 *	 3. found *     *       *
		 *	 4. found *       *       *
		 *	 5. found *         *
		 *	 6. found *           *
		 *	 7. found *             *
		 *	 8. found *               *
		 *	 9. found *                 *
		 *	10. found *
		 *	11. found random insertion
		 */
		/* FIXME: Maybe use the rarity index to get a ``better'' random
		 * piece which can be downloaded from multiple peers as opposed
		 * to the purpose of the rarest first strategy. */
		if (places >= 2) {
			int skip = sizeof_array(pieces) / places;
			int pos;

			for (pos = 0; pos < sizeof_array(pieces); pos += skip)
				pieces[pos] = piece;

			places /= 2;

		} else {
			pieces[randomize(sizeof_array(pieces))] = piece;
		}
	}

	return pieces[randomize(sizeof_array(pieces))];
}

/* Search for the rarest piece that is available from the peer. */
static uint32_t
find_rarest_in_bittorrent_piece_cache(struct bittorrent_piece_cache *cache,
				      struct bittorrent_peer_connection *peer)
{
	uint32_t pieces[] = {
		BITTORRENT_PIECE_UNDEF, BITTORRENT_PIECE_UNDEF,
		BITTORRENT_PIECE_UNDEF, BITTORRENT_PIECE_UNDEF,
		BITTORRENT_PIECE_UNDEF, BITTORRENT_PIECE_UNDEF,
		BITTORRENT_PIECE_UNDEF, BITTORRENT_PIECE_UNDEF,
		BITTORRENT_PIECE_UNDEF, BITTORRENT_PIECE_UNDEF,
		BITTORRENT_PIECE_UNDEF, BITTORRENT_PIECE_UNDEF,
		BITTORRENT_PIECE_UNDEF, BITTORRENT_PIECE_UNDEF,
		BITTORRENT_PIECE_UNDEF, BITTORRENT_PIECE_UNDEF,
		BITTORRENT_PIECE_UNDEF, BITTORRENT_PIECE_UNDEF,
		BITTORRENT_PIECE_UNDEF, BITTORRENT_PIECE_UNDEF,
	};
	int places = sizeof_array(pieces);
	uint16_t piece_rarity = BITTORRENT_PIECE_RARITY_UNDEF;
	uint32_t piece;

	assert(peer->bitfield->bitsize == peer->bittorrent->meta.pieces);

	srand(time(NULL));

	/* Try to randomize the piece picking using the strategy from the random
	 * piece selection. */
	foreachback_bitfield_set (piece, peer->bitfield) {
		struct bittorrent_piece_cache_entry *entry;
		int pos, skip = sizeof_array(pieces) / places;

		entry = &cache->entries[piece];

		assertm(entry->rarity, "Piece cache out of sync");

		if (!entry->remaining || entry->rarity > piece_rarity)
			continue;

		if (entry->rarity < piece_rarity) {
			places = sizeof_array(pieces);
			piece_rarity = entry->rarity;

		} else if (places < 2) {
			pieces[randomize(sizeof_array(pieces))] = piece;
			continue;
		}

		skip = sizeof_array(pieces) / places;

		for (pos = 0; pos < sizeof_array(pieces); pos += skip)
			pieces[pos] = piece;

		places /= 2;
	}

	return pieces[randomize(sizeof_array(pieces))];
}

/* Search for a clonable request that is available from the peer. */
static struct bittorrent_peer_request *
find_clonable_bittorrent_peer_request(struct bittorrent_peer_connection *peer)
{
	struct bittorrent_piece_cache *cache = peer->bittorrent->cache;
	struct bittorrent_peer_connection *active_peer;
	struct bittorrent_peer_request *clone = NULL;
	uint16_t clone_rarity = BITTORRENT_PIECE_RARITY_UNDEF;

	foreach (active_peer, peer->bittorrent->peers) {
		struct bittorrent_peer_request *request, *clone = NULL;

		foreach (request, active_peer->local.requests) {
			uint16_t request_rarity;

			/* Check the the peer doesn't already have the complete
			 * piece or request. */
			if (!test_bitfield_bit(peer->bitfield, request->piece)
			    || find_local_bittorrent_peer_request(peer, request))
				continue;

			/* Prefer to clone requests which have not been cloned
			 * yet. */
			if (!request->cloned)
				return request;

			request_rarity = cache->entries[request->piece].rarity;

			/* If there are only already cloned requests left
			 * clone the rarest. */
			if (request_rarity >= clone_rarity)
				continue;

			clone	     = request;
			clone_rarity = request_rarity;
		}
	}

	return clone;
}

static struct bittorrent_peer_request *
clone_bittorrent_peer_request(struct bittorrent_peer_request *request)
{
	struct bittorrent_peer_request *clone;

	clone = mem_alloc(sizeof(*clone));
	if (!clone) return NULL;

	/* Both are now clones ... */
	request->cloned = 1;

	copy_struct(clone, request);

	/* ... but the new clone has not yet been requested. */
	clone->requested = 0;

	return clone;
}

/* Split the piece into multiple requests and add them to the free list
 * except for the first request which is returned. */
static struct bittorrent_peer_request *
add_piece_to_bittorrent_free_list(struct bittorrent_piece_cache *cache,
				  struct bittorrent_connection *bittorrent,
				  uint32_t piece)
{
	struct bittorrent_peer_request *request, *next;
	uint32_t request_length, piece_length, piece_offset;
	INIT_LIST_HEAD(requests);
	uint16_t blocks = 0;

	assert(piece <= bittorrent->meta.pieces);

	piece_offset	= 0;
	piece_length	= get_bittorrent_piece_length(&bittorrent->meta, piece);
	request_length	= get_opt_int("protocol.bittorrent.peerwire.request_length");

	if (request_length > piece_length)
		request_length = piece_length;

	assertm(piece_length, "Default piece length unset");

	/* First initialize and add all pieces to the local request list. */
	do {
		request = mem_calloc(1, sizeof(*request));
		if (!request) break;

		request->piece  = piece;
		request->offset = piece_offset;
		/* The last block might have to be smaller. */
		request->length = piece_offset + request_length > piece_length
				? piece_length - piece_offset
				: request_length;
		request->block  = blocks++;

		piece_offset += request->length;
		add_to_list_end(requests, request);

	} while (piece_offset < piece_length);

	/* Make sure that requests was created for the entire piece. */
	if (piece_offset < piece_length) {
		free_list(requests);
		return NULL;
	}

	assertm(piece_offset == piece_length);
	assertm(blocks, "Piece was not divided into blocks");
	assert(!cache->entries[piece].blocks);

	cache->entries[piece].blocks = init_bitfield(blocks);
	if (!cache->entries[piece].blocks) {
		free_list(requests);
		return NULL;
	}

	set_bittorrent_piece_cache_remaining(cache, piece, -1);

	assertm(cache->remaining_pieces < bittorrent->meta.pieces,
		"Cache count underflow");

	/* Actually move the requests to the free list, except the last one. */
	foreachsafe (request, next, requests) {
		del_from_list(request);
		if (list_empty(requests))
			return request;
		add_to_list_end(cache->free_list, request);
	}

	/* XXX: Should never happen! */
	INTERNAL("Bad request list appending.");
	return NULL;
}

struct bittorrent_peer_request *
find_bittorrent_peer_request(struct bittorrent_peer_connection *peer)
{
	struct bittorrent_connection *bittorrent = peer->bittorrent;
	struct bittorrent_piece_cache *cache = bittorrent->cache;
	struct bittorrent_peer_request *request;
	uint32_t piece;

	/* First try to browse the free list ... */

	if (list_empty(cache->free_list)) {
		/* Enter the end game mode when all remaining pieces have been
		 * requested. */
		if (cache->remaining_pieces == 0)
			bittorrent->mode = BITTORRENT_MODE_END_GAME;

	} else {
		request = find_bittorrent_free_list_peer_request(cache, peer);
		if (request) return request;
	}

	/* Are there remaining pieces? */

	switch (bittorrent->mode) {
	case BITTORRENT_MODE_PIECELESS:
		/* Find a random piece available from the peer. */
		piece = find_random_in_bittorrent_piece_cache(cache, peer);
		break;

	case BITTORRENT_MODE_NORMAL:
		/* Find the rarest piece available from the peer. */
		piece = find_rarest_in_bittorrent_piece_cache(cache, peer);
		break;

	case BITTORRENT_MODE_END_GAME:
		assert(cache->remaining_pieces == 0);
		request = find_clonable_bittorrent_peer_request(peer);
		if (!request) return NULL;

		return clone_bittorrent_peer_request(request);

	case BITTORRENT_MODE_SEEDER:
	default:
		INTERNAL("Not able to find peer request");
		return NULL;