diff options
author | Bertrand Marc <beberking@gmail.com> | 2012-05-02 21:43:37 +0200 |
---|---|---|
committer | Bertrand Marc <beberking@gmail.com> | 2012-05-02 21:43:37 +0200 |
commit | 2b81464a43485fcc8ce079fafdee7b7a171835f4 (patch) | |
tree | 394774c0f735199b57d51a2d3840356317853fe1 /src/fragmentation |
Imported Upstream version 0.9.2upstream/0.9.2
Diffstat (limited to 'src/fragmentation')
-rw-r--r-- | src/fragmentation/Makefile.am | 36 | ||||
-rw-r--r-- | src/fragmentation/Makefile.in | 785 | ||||
-rw-r--r-- | src/fragmentation/defragmentation.c | 547 | ||||
-rw-r--r-- | src/fragmentation/fragmentation.c | 405 | ||||
-rw-r--r-- | src/fragmentation/fragmentation.h | 89 | ||||
-rw-r--r-- | src/fragmentation/test_fragmentation.c | 261 | ||||
-rw-r--r-- | src/fragmentation/test_fragmentation_data.conf | 5 |
7 files changed, 2128 insertions, 0 deletions
diff --git a/src/fragmentation/Makefile.am b/src/fragmentation/Makefile.am new file mode 100644 index 0000000..1cdbefc --- /dev/null +++ b/src/fragmentation/Makefile.am @@ -0,0 +1,36 @@ +INCLUDES = -I$(top_srcdir)/src/include + +if MINGW + WINFLAGS = -Wl,--no-undefined -Wl,--export-all-symbols +endif + +if USE_COVERAGE + AM_CFLAGS = --coverage +endif + +lib_LTLIBRARIES = libgnunetfragmentation.la + +libgnunetfragmentation_la_SOURCES = \ + fragmentation.c fragmentation.h \ + defragmentation.c +libgnunetfragmentation_la_LIBADD = -lm \ + $(top_builddir)/src/statistics/libgnunetstatistics.la \ + $(top_builddir)/src/util/libgnunetutil.la +libgnunetfragmentation_la_LDFLAGS = \ + $(GN_LIB_LDFLAGS) \ + -version-info 0:0:0 + +check_PROGRAMS = \ + test_fragmentation + +if ENABLE_TEST_RUN +TESTS = $(check_PROGRAMS) +endif + +test_fragmentation_SOURCES = \ + test_fragmentation.c +test_fragmentation_LDADD = \ + $(top_builddir)/src/fragmentation/libgnunetfragmentation.la \ + $(top_builddir)/src/util/libgnunetutil.la + +EXTRA_DIST = test_fragmentation_data.conf
\ No newline at end of file diff --git a/src/fragmentation/Makefile.in b/src/fragmentation/Makefile.in new file mode 100644 index 0000000..2ccad77 --- /dev/null +++ b/src/fragmentation/Makefile.in @@ -0,0 +1,785 @@ +# Makefile.in generated by automake 1.11.1 from Makefile.am. +# @configure_input@ + +# Copyright (C) 1994, 1995, 1996, 1997, 1998, 1999, 2000, 2001, 2002, +# 2003, 2004, 2005, 2006, 2007, 2008, 2009 Free Software Foundation, +# Inc. +# This Makefile.in is free software; the Free Software Foundation +# gives unlimited permission to copy and/or distribute it, +# with or without modifications, as long as this notice is preserved. + +# This program is distributed in the hope that it will be useful, +# but WITHOUT ANY WARRANTY, to the extent permitted by law; without +# even the implied warranty of MERCHANTABILITY or FITNESS FOR A +# PARTICULAR PURPOSE. + +@SET_MAKE@ + +VPATH = @srcdir@ +pkgdatadir = $(datadir)/@PACKAGE@ +pkgincludedir = $(includedir)/@PACKAGE@ +pkglibdir = $(libdir)/@PACKAGE@ +pkglibexecdir = $(libexecdir)/@PACKAGE@ +am__cd = CDPATH="$${ZSH_VERSION+.}$(PATH_SEPARATOR)" && cd +install_sh_DATA = $(install_sh) -c -m 644 +install_sh_PROGRAM = $(install_sh) -c +install_sh_SCRIPT = $(install_sh) -c +INSTALL_HEADER = $(INSTALL_DATA) +transform = $(program_transform_name) +NORMAL_INSTALL = : +PRE_INSTALL = : +POST_INSTALL = : +NORMAL_UNINSTALL = : +PRE_UNINSTALL = : +POST_UNINSTALL = : +build_triplet = @build@ +host_triplet = @host@ +target_triplet = @target@ +check_PROGRAMS = test_fragmentation$(EXEEXT) +subdir = src/fragmentation +DIST_COMMON = $(srcdir)/Makefile.am $(srcdir)/Makefile.in +ACLOCAL_M4 = $(top_srcdir)/aclocal.m4 +am__aclocal_m4_deps = $(top_srcdir)/m4/absolute-header.m4 \ + $(top_srcdir)/m4/align.m4 $(top_srcdir)/m4/argz.m4 \ + $(top_srcdir)/m4/gettext.m4 $(top_srcdir)/m4/iconv.m4 \ + $(top_srcdir)/m4/lib-ld.m4 $(top_srcdir)/m4/lib-link.m4 \ + $(top_srcdir)/m4/lib-prefix.m4 $(top_srcdir)/m4/libcurl.m4 \ + $(top_srcdir)/m4/libgcrypt.m4 $(top_srcdir)/m4/libtool.m4 \ + $(top_srcdir)/m4/libunistring.m4 $(top_srcdir)/m4/ltdl.m4 \ + $(top_srcdir)/m4/ltoptions.m4 $(top_srcdir)/m4/ltsugar.m4 \ + $(top_srcdir)/m4/ltversion.m4 $(top_srcdir)/m4/lt~obsolete.m4 \ + $(top_srcdir)/m4/nls.m4 $(top_srcdir)/m4/po.m4 \ + $(top_srcdir)/m4/progtest.m4 $(top_srcdir)/acinclude.m4 \ + $(top_srcdir)/configure.ac +am__configure_deps = $(am__aclocal_m4_deps) $(CONFIGURE_DEPENDENCIES) \ + $(ACLOCAL_M4) +mkinstalldirs = $(install_sh) -d +CONFIG_HEADER = $(top_builddir)/gnunet_config.h +CONFIG_CLEAN_FILES = +CONFIG_CLEAN_VPATH_FILES = +am__vpath_adj_setup = srcdirstrip=`echo "$(srcdir)" | sed 's|.|.|g'`; +am__vpath_adj = case $$p in \ + $(srcdir)/*) f=`echo "$$p" | sed "s|^$$srcdirstrip/||"`;; \ + *) f=$$p;; \ + esac; +am__strip_dir = f=`echo $$p | sed -e 's|^.*/||'`; +am__install_max = 40 +am__nobase_strip_setup = \ + srcdirstrip=`echo "$(srcdir)" | sed 's/[].[^$$\\*|]/\\\\&/g'` +am__nobase_strip = \ + for p in $$list; do echo "$$p"; done | sed -e "s|$$srcdirstrip/||" +am__nobase_list = $(am__nobase_strip_setup); \ + for p in $$list; do echo "$$p $$p"; done | \ + sed "s| $$srcdirstrip/| |;"' / .*\//!s/ .*/ ./; s,\( .*\)/[^/]*$$,\1,' | \ + $(AWK) 'BEGIN { files["."] = "" } { files[$$2] = files[$$2] " " $$1; \ + if (++n[$$2] == $(am__install_max)) \ + { print $$2, files[$$2]; n[$$2] = 0; files[$$2] = "" } } \ + END { for (dir in files) print dir, files[dir] }' +am__base_list = \ + sed '$$!N;$$!N;$$!N;$$!N;$$!N;$$!N;$$!N;s/\n/ /g' | \ + sed '$$!N;$$!N;$$!N;$$!N;s/\n/ /g' +am__installdirs = "$(DESTDIR)$(libdir)" +LTLIBRARIES = $(lib_LTLIBRARIES) +libgnunetfragmentation_la_DEPENDENCIES = \ + $(top_builddir)/src/statistics/libgnunetstatistics.la \ + $(top_builddir)/src/util/libgnunetutil.la +am_libgnunetfragmentation_la_OBJECTS = fragmentation.lo \ + defragmentation.lo +libgnunetfragmentation_la_OBJECTS = \ + $(am_libgnunetfragmentation_la_OBJECTS) +AM_V_lt = $(am__v_lt_$(V)) +am__v_lt_ = $(am__v_lt_$(AM_DEFAULT_VERBOSITY)) +am__v_lt_0 = --silent +libgnunetfragmentation_la_LINK = $(LIBTOOL) $(AM_V_lt) --tag=CC \ + $(AM_LIBTOOLFLAGS) $(LIBTOOLFLAGS) --mode=link $(CCLD) \ + $(AM_CFLAGS) $(CFLAGS) $(libgnunetfragmentation_la_LDFLAGS) \ + $(LDFLAGS) -o $@ +am_test_fragmentation_OBJECTS = test_fragmentation.$(OBJEXT) +test_fragmentation_OBJECTS = $(am_test_fragmentation_OBJECTS) +test_fragmentation_DEPENDENCIES = \ + $(top_builddir)/src/fragmentation/libgnunetfragmentation.la \ + $(top_builddir)/src/util/libgnunetutil.la +DEFAULT_INCLUDES = -I.@am__isrc@ -I$(top_builddir) +depcomp = $(SHELL) $(top_srcdir)/depcomp +am__depfiles_maybe = depfiles +am__mv = mv -f +COMPILE = $(CC) $(DEFS) $(DEFAULT_INCLUDES) $(INCLUDES) $(AM_CPPFLAGS) \ + $(CPPFLAGS) $(AM_CFLAGS) $(CFLAGS) +LTCOMPILE = $(LIBTOOL) $(AM_V_lt) --tag=CC $(AM_LIBTOOLFLAGS) \ + $(LIBTOOLFLAGS) --mode=compile $(CC) $(DEFS) \ + $(DEFAULT_INCLUDES) $(INCLUDES) $(AM_CPPFLAGS) $(CPPFLAGS) \ + $(AM_CFLAGS) $(CFLAGS) +AM_V_CC = $(am__v_CC_$(V)) +am__v_CC_ = $(am__v_CC_$(AM_DEFAULT_VERBOSITY)) +am__v_CC_0 = @echo " CC " $@; +AM_V_at = $(am__v_at_$(V)) +am__v_at_ = $(am__v_at_$(AM_DEFAULT_VERBOSITY)) +am__v_at_0 = @ +CCLD = $(CC) +LINK = $(LIBTOOL) $(AM_V_lt) --tag=CC $(AM_LIBTOOLFLAGS) \ + $(LIBTOOLFLAGS) --mode=link $(CCLD) $(AM_CFLAGS) $(CFLAGS) \ + $(AM_LDFLAGS) $(LDFLAGS) -o $@ +AM_V_CCLD = $(am__v_CCLD_$(V)) +am__v_CCLD_ = $(am__v_CCLD_$(AM_DEFAULT_VERBOSITY)) +am__v_CCLD_0 = @echo " CCLD " $@; +AM_V_GEN = $(am__v_GEN_$(V)) +am__v_GEN_ = $(am__v_GEN_$(AM_DEFAULT_VERBOSITY)) +am__v_GEN_0 = @echo " GEN " $@; +SOURCES = $(libgnunetfragmentation_la_SOURCES) \ + $(test_fragmentation_SOURCES) +DIST_SOURCES = $(libgnunetfragmentation_la_SOURCES) \ + $(test_fragmentation_SOURCES) +ETAGS = etags +CTAGS = ctags +am__tty_colors = \ +red=; grn=; lgn=; blu=; std= +DISTFILES = $(DIST_COMMON) $(DIST_SOURCES) $(TEXINFOS) $(EXTRA_DIST) +ACLOCAL = @ACLOCAL@ +AMTAR = @AMTAR@ +AM_DEFAULT_VERBOSITY = @AM_DEFAULT_VERBOSITY@ +AR = @AR@ +ARGZ_H = @ARGZ_H@ +AS = @AS@ +AUTOCONF = @AUTOCONF@ +AUTOHEADER = @AUTOHEADER@ +AUTOMAKE = @AUTOMAKE@ +AWK = @AWK@ +CC = @CC@ +CCDEPMODE = @CCDEPMODE@ +CFLAGS = @CFLAGS@ +CPP = @CPP@ +CPPFLAGS = @CPPFLAGS@ +CXX = @CXX@ +CXXCPP = @CXXCPP@ +CXXDEPMODE = @CXXDEPMODE@ +CXXFLAGS = @CXXFLAGS@ +CYGPATH_W = @CYGPATH_W@ +DEFAULT_INTERFACE = @DEFAULT_INTERFACE@ +DEFS = @DEFS@ +DEPDIR = @DEPDIR@ +DLLDIR = @DLLDIR@ +DLLTOOL = @DLLTOOL@ +DSYMUTIL = @DSYMUTIL@ +DUMPBIN = @DUMPBIN@ +ECHO_C = @ECHO_C@ +ECHO_N = @ECHO_N@ +ECHO_T = @ECHO_T@ +EGREP = @EGREP@ +EXEEXT = @EXEEXT@ +EXT_LIBS = @EXT_LIBS@ +EXT_LIB_PATH = @EXT_LIB_PATH@ +FGREP = @FGREP@ +GMSGFMT = @GMSGFMT@ +GMSGFMT_015 = @GMSGFMT_015@ +GNUNETDNS_GROUP = @GNUNETDNS_GROUP@ +GN_DAEMON_CONFIG_DIR = @GN_DAEMON_CONFIG_DIR@ +GN_DAEMON_HOME_DIR = @GN_DAEMON_HOME_DIR@ +GN_INTLINCL = @GN_INTLINCL@ +GN_LIBINTL = @GN_LIBINTL@ +GN_LIB_LDFLAGS = @GN_LIB_LDFLAGS@ +GN_PLUGIN_LDFLAGS = @GN_PLUGIN_LDFLAGS@ +GN_USER_HOME_DIR = @GN_USER_HOME_DIR@ +GREP = @GREP@ +HAVE_LIBUNISTRING = @HAVE_LIBUNISTRING@ +INCLTDL = @INCLTDL@ +INSTALL = @INSTALL@ +INSTALL_DATA = @INSTALL_DATA@ +INSTALL_PROGRAM = @INSTALL_PROGRAM@ +INSTALL_SCRIPT = @INSTALL_SCRIPT@ +INSTALL_STRIP_PROGRAM = @INSTALL_STRIP_PROGRAM@ +INTLLIBS = @INTLLIBS@ +INTL_MACOSX_LIBS = @INTL_MACOSX_LIBS@ +LD = @LD@ +LDFLAGS = @LDFLAGS@ +LIBADD_DL = @LIBADD_DL@ +LIBADD_DLD_LINK = @LIBADD_DLD_LINK@ +LIBADD_DLOPEN = @LIBADD_DLOPEN@ +LIBADD_SHL_LOAD = @LIBADD_SHL_LOAD@ +LIBCURL = @LIBCURL@ +LIBCURL_CPPFLAGS = @LIBCURL_CPPFLAGS@ +LIBGCRYPT_CFLAGS = @LIBGCRYPT_CFLAGS@ +LIBGCRYPT_CONFIG = @LIBGCRYPT_CONFIG@ +LIBGCRYPT_LIBS = @LIBGCRYPT_LIBS@ +LIBICONV = @LIBICONV@ +LIBINTL = @LIBINTL@ +LIBLTDL = @LIBLTDL@ +LIBOBJS = @LIBOBJS@ +LIBPREFIX = @LIBPREFIX@ +LIBS = @LIBS@ +LIBTOOL = @LIBTOOL@ +LIBUNISTRING = @LIBUNISTRING@ +LIPO = @LIPO@ +LN_S = @LN_S@ +LTDLDEPS = @LTDLDEPS@ +LTDLINCL = @LTDLINCL@ +LTDLOPEN = @LTDLOPEN@ +LTLIBICONV = @LTLIBICONV@ +LTLIBINTL = @LTLIBINTL@ +LTLIBOBJS = @LTLIBOBJS@ +LTLIBUNISTRING = @LTLIBUNISTRING@ +LT_CONFIG_H = @LT_CONFIG_H@ +LT_DLLOADERS = @LT_DLLOADERS@ +LT_DLPREOPEN = @LT_DLPREOPEN@ +MAKEINFO = @MAKEINFO@ +MKDIR_P = @MKDIR_P@ +MSGFMT = @MSGFMT@ +MSGFMT_015 = @MSGFMT_015@ +MSGMERGE = @MSGMERGE@ +MYSQL_CPPFLAGS = @MYSQL_CPPFLAGS@ +MYSQL_LDFLAGS = @MYSQL_LDFLAGS@ +NM = @NM@ +NMEDIT = @NMEDIT@ +OBJC = @OBJC@ +OBJCDEPMODE = @OBJCDEPMODE@ +OBJCFLAGS = @OBJCFLAGS@ +OBJDUMP = @OBJDUMP@ +OBJEXT = @OBJEXT@ +OTOOL = @OTOOL@ +OTOOL64 = @OTOOL64@ +PACKAGE = @PACKAGE@ +PACKAGE_BUGREPORT = @PACKAGE_BUGREPORT@ +PACKAGE_NAME = @PACKAGE_NAME@ +PACKAGE_STRING = @PACKAGE_STRING@ +PACKAGE_TARNAME = @PACKAGE_TARNAME@ +PACKAGE_URL = @PACKAGE_URL@ +PACKAGE_VERSION = @PACKAGE_VERSION@ +PATH_SEPARATOR = @PATH_SEPARATOR@ +POSTGRES_CPPFLAGS = @POSTGRES_CPPFLAGS@ +POSTGRES_LDFLAGS = @POSTGRES_LDFLAGS@ +POSUB = @POSUB@ +PYTHON = @PYTHON@ +PYTHON_EXEC_PREFIX = @PYTHON_EXEC_PREFIX@ +PYTHON_PLATFORM = @PYTHON_PLATFORM@ +PYTHON_PREFIX = @PYTHON_PREFIX@ +PYTHON_VERSION = @PYTHON_VERSION@ +RANLIB = @RANLIB@ +SED = @SED@ +SET_MAKE = @SET_MAKE@ +SHELL = @SHELL@ +SQLITE_CPPFLAGS = @SQLITE_CPPFLAGS@ +SQLITE_LDFLAGS = @SQLITE_LDFLAGS@ +STRIP = @STRIP@ +SUDO_BINARY = @SUDO_BINARY@ +UNIXONLY = @UNIXONLY@ +USE_NLS = @USE_NLS@ +VERSION = @VERSION@ +XGETTEXT = @XGETTEXT@ +XGETTEXT_015 = @XGETTEXT_015@ +XMKMF = @XMKMF@ +X_CFLAGS = @X_CFLAGS@ +X_EXTRA_LIBS = @X_EXTRA_LIBS@ +X_LIBS = @X_LIBS@ +X_PRE_LIBS = @X_PRE_LIBS@ +_libcurl_config = @_libcurl_config@ +abs_builddir = @abs_builddir@ +abs_srcdir = @abs_srcdir@ +abs_top_builddir = @abs_top_builddir@ +abs_top_srcdir = @abs_top_srcdir@ +ac_ct_CC = @ac_ct_CC@ +ac_ct_CXX = @ac_ct_CXX@ +ac_ct_DUMPBIN = @ac_ct_DUMPBIN@ +ac_ct_OBJC = @ac_ct_OBJC@ +am__include = @am__include@ +am__leading_dot = @am__leading_dot@ +am__quote = @am__quote@ +am__tar = @am__tar@ +am__untar = @am__untar@ +bindir = @bindir@ +build = @build@ +build_alias = @build_alias@ +build_cpu = @build_cpu@ +build_os = @build_os@ +build_target = @build_target@ +build_vendor = @build_vendor@ +builddir = @builddir@ +datadir = @datadir@ +datarootdir = @datarootdir@ +docdir = @docdir@ +dvidir = @dvidir@ +exec_prefix = @exec_prefix@ +host = @host@ +host_alias = @host_alias@ +host_cpu = @host_cpu@ +host_os = @host_os@ +host_vendor = @host_vendor@ +htmldir = @htmldir@ +includedir = @includedir@ +infodir = @infodir@ +install_sh = @install_sh@ +libdir = @libdir@ +libexecdir = @libexecdir@ +localedir = @localedir@ +localstatedir = @localstatedir@ +lt_ECHO = @lt_ECHO@ +ltdl_LIBOBJS = @ltdl_LIBOBJS@ +ltdl_LTLIBOBJS = @ltdl_LTLIBOBJS@ +mandir = @mandir@ +mkdir_p = @mkdir_p@ +oldincludedir = @oldincludedir@ +pdfdir = @pdfdir@ +pkgpyexecdir = @pkgpyexecdir@ +pkgpythondir = @pkgpythondir@ +prefix = @prefix@ +program_transform_name = @program_transform_name@ +psdir = @psdir@ +pyexecdir = @pyexecdir@ +pythondir = @pythondir@ +sbindir = @sbindir@ +sharedstatedir = @sharedstatedir@ +srcdir = @srcdir@ +subdirs = @subdirs@ +sys_symbol_underscore = @sys_symbol_underscore@ +sysconfdir = @sysconfdir@ +target = @target@ +target_alias = @target_alias@ +target_cpu = @target_cpu@ +target_os = @target_os@ +target_vendor = @target_vendor@ +top_build_prefix = @top_build_prefix@ +top_builddir = @top_builddir@ +top_srcdir = @top_srcdir@ +INCLUDES = -I$(top_srcdir)/src/include +@MINGW_TRUE@WINFLAGS = -Wl,--no-undefined -Wl,--export-all-symbols +@USE_COVERAGE_TRUE@AM_CFLAGS = --coverage +lib_LTLIBRARIES = libgnunetfragmentation.la +libgnunetfragmentation_la_SOURCES = \ + fragmentation.c fragmentation.h \ + defragmentation.c + +libgnunetfragmentation_la_LIBADD = -lm \ + $(top_builddir)/src/statistics/libgnunetstatistics.la \ + $(top_builddir)/src/util/libgnunetutil.la + +libgnunetfragmentation_la_LDFLAGS = \ + $(GN_LIB_LDFLAGS) \ + -version-info 0:0:0 + +@ENABLE_TEST_RUN_TRUE@TESTS = $(check_PROGRAMS) +test_fragmentation_SOURCES = \ + test_fragmentation.c + +test_fragmentation_LDADD = \ + $(top_builddir)/src/fragmentation/libgnunetfragmentation.la \ + $(top_builddir)/src/util/libgnunetutil.la + +EXTRA_DIST = test_fragmentation_data.conf +all: all-am + +.SUFFIXES: +.SUFFIXES: .c .lo .o .obj +$(srcdir)/Makefile.in: $(srcdir)/Makefile.am $(am__configure_deps) + @for dep in $?; do \ + case '$(am__configure_deps)' in \ + *$$dep*) \ + ( cd $(top_builddir) && $(MAKE) $(AM_MAKEFLAGS) am--refresh ) \ + && { if test -f $@; then exit 0; else break; fi; }; \ + exit 1;; \ + esac; \ + done; \ + echo ' cd $(top_srcdir) && $(AUTOMAKE) --gnu src/fragmentation/Makefile'; \ + $(am__cd) $(top_srcdir) && \ + $(AUTOMAKE) --gnu src/fragmentation/Makefile +.PRECIOUS: Makefile +Makefile: $(srcdir)/Makefile.in $(top_builddir)/config.status + @case '$?' in \ + *config.status*) \ + cd $(top_builddir) && $(MAKE) $(AM_MAKEFLAGS) am--refresh;; \ + *) \ + echo ' cd $(top_builddir) && $(SHELL) ./config.status $(subdir)/$@ $(am__depfiles_maybe)'; \ + cd $(top_builddir) && $(SHELL) ./config.status $(subdir)/$@ $(am__depfiles_maybe);; \ + esac; + +$(top_builddir)/config.status: $(top_srcdir)/configure $(CONFIG_STATUS_DEPENDENCIES) + cd $(top_builddir) && $(MAKE) $(AM_MAKEFLAGS) am--refresh + +$(top_srcdir)/configure: $(am__configure_deps) + cd $(top_builddir) && $(MAKE) $(AM_MAKEFLAGS) am--refresh +$(ACLOCAL_M4): $(am__aclocal_m4_deps) + cd $(top_builddir) && $(MAKE) $(AM_MAKEFLAGS) am--refresh +$(am__aclocal_m4_deps): +install-libLTLIBRARIES: $(lib_LTLIBRARIES) + @$(NORMAL_INSTALL) + test -z "$(libdir)" || $(MKDIR_P) "$(DESTDIR)$(libdir)" + @list='$(lib_LTLIBRARIES)'; test -n "$(libdir)" || list=; \ + list2=; for p in $$list; do \ + if test -f $$p; then \ + list2="$$list2 $$p"; \ + else :; fi; \ + done; \ + test -z "$$list2" || { \ + echo " $(LIBTOOL) $(AM_LIBTOOLFLAGS) $(LIBTOOLFLAGS) --mode=install $(INSTALL) $(INSTALL_STRIP_FLAG) $$list2 '$(DESTDIR)$(libdir)'"; \ + $(LIBTOOL) $(AM_LIBTOOLFLAGS) $(LIBTOOLFLAGS) --mode=install $(INSTALL) $(INSTALL_STRIP_FLAG) $$list2 "$(DESTDIR)$(libdir)"; \ + } + +uninstall-libLTLIBRARIES: + @$(NORMAL_UNINSTALL) + @list='$(lib_LTLIBRARIES)'; test -n "$(libdir)" || list=; \ + for p in $$list; do \ + $(am__strip_dir) \ + echo " $(LIBTOOL) $(AM_LIBTOOLFLAGS) $(LIBTOOLFLAGS) --mode=uninstall rm -f '$(DESTDIR)$(libdir)/$$f'"; \ + $(LIBTOOL) $(AM_LIBTOOLFLAGS) $(LIBTOOLFLAGS) --mode=uninstall rm -f "$(DESTDIR)$(libdir)/$$f"; \ + done + +clean-libLTLIBRARIES: + -test -z "$(lib_LTLIBRARIES)" || rm -f $(lib_LTLIBRARIES) + @list='$(lib_LTLIBRARIES)'; for p in $$list; do \ + dir="`echo $$p | sed -e 's|/[^/]*$$||'`"; \ + test "$$dir" != "$$p" || dir=.; \ + echo "rm -f \"$${dir}/so_locations\""; \ + rm -f "$${dir}/so_locations"; \ + done +libgnunetfragmentation.la: $(libgnunetfragmentation_la_OBJECTS) $(libgnunetfragmentation_la_DEPENDENCIES) + $(AM_V_CCLD)$(libgnunetfragmentation_la_LINK) -rpath $(libdir) $(libgnunetfragmentation_la_OBJECTS) $(libgnunetfragmentation_la_LIBADD) $(LIBS) + +clean-checkPROGRAMS: + @list='$(check_PROGRAMS)'; test -n "$$list" || exit 0; \ + echo " rm -f" $$list; \ + rm -f $$list || exit $$?; \ + test -n "$(EXEEXT)" || exit 0; \ + list=`for p in $$list; do echo "$$p"; done | sed 's/$(EXEEXT)$$//'`; \ + echo " rm -f" $$list; \ + rm -f $$list +test_fragmentation$(EXEEXT): $(test_fragmentation_OBJECTS) $(test_fragmentation_DEPENDENCIES) + @rm -f test_fragmentation$(EXEEXT) + $(AM_V_CCLD)$(LINK) $(test_fragmentation_OBJECTS) $(test_fragmentation_LDADD) $(LIBS) + +mostlyclean-compile: + -rm -f *.$(OBJEXT) + +distclean-compile: + -rm -f *.tab.c + +@AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/defragmentation.Plo@am__quote@ +@AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/fragmentation.Plo@am__quote@ +@AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/test_fragmentation.Po@am__quote@ + +.c.o: +@am__fastdepCC_TRUE@ $(AM_V_CC)$(COMPILE) -MT $@ -MD -MP -MF $(DEPDIR)/$*.Tpo -c -o $@ $< +@am__fastdepCC_TRUE@ $(AM_V_at)$(am__mv) $(DEPDIR)/$*.Tpo $(DEPDIR)/$*.Po +@am__fastdepCC_FALSE@ $(AM_V_CC) @AM_BACKSLASH@ +@AMDEP_TRUE@@am__fastdepCC_FALSE@ source='$<' object='$@' libtool=no @AMDEPBACKSLASH@ +@AMDEP_TRUE@@am__fastdepCC_FALSE@ DEPDIR=$(DEPDIR) $(CCDEPMODE) $(depcomp) @AMDEPBACKSLASH@ +@am__fastdepCC_FALSE@ $(COMPILE) -c $< + +.c.obj: +@am__fastdepCC_TRUE@ $(AM_V_CC)$(COMPILE) -MT $@ -MD -MP -MF $(DEPDIR)/$*.Tpo -c -o $@ `$(CYGPATH_W) '$<'` +@am__fastdepCC_TRUE@ $(AM_V_at)$(am__mv) $(DEPDIR)/$*.Tpo $(DEPDIR)/$*.Po +@am__fastdepCC_FALSE@ $(AM_V_CC) @AM_BACKSLASH@ +@AMDEP_TRUE@@am__fastdepCC_FALSE@ source='$<' object='$@' libtool=no @AMDEPBACKSLASH@ +@AMDEP_TRUE@@am__fastdepCC_FALSE@ DEPDIR=$(DEPDIR) $(CCDEPMODE) $(depcomp) @AMDEPBACKSLASH@ +@am__fastdepCC_FALSE@ $(COMPILE) -c `$(CYGPATH_W) '$<'` + +.c.lo: +@am__fastdepCC_TRUE@ $(AM_V_CC)$(LTCOMPILE) -MT $@ -MD -MP -MF $(DEPDIR)/$*.Tpo -c -o $@ $< +@am__fastdepCC_TRUE@ $(AM_V_at)$(am__mv) $(DEPDIR)/$*.Tpo $(DEPDIR)/$*.Plo +@am__fastdepCC_FALSE@ $(AM_V_CC) @AM_BACKSLASH@ +@AMDEP_TRUE@@am__fastdepCC_FALSE@ source='$<' object='$@' libtool=yes @AMDEPBACKSLASH@ +@AMDEP_TRUE@@am__fastdepCC_FALSE@ DEPDIR=$(DEPDIR) $(CCDEPMODE) $(depcomp) @AMDEPBACKSLASH@ +@am__fastdepCC_FALSE@ $(LTCOMPILE) -c -o $@ $< + +mostlyclean-libtool: + -rm -f *.lo + +clean-libtool: + -rm -rf .libs _libs + +ID: $(HEADERS) $(SOURCES) $(LISP) $(TAGS_FILES) + list='$(SOURCES) $(HEADERS) $(LISP) $(TAGS_FILES)'; \ + unique=`for i in $$list; do \ + if test -f "$$i"; then echo $$i; else echo $(srcdir)/$$i; fi; \ + done | \ + $(AWK) '{ files[$$0] = 1; nonempty = 1; } \ + END { if (nonempty) { for (i in files) print i; }; }'`; \ + mkid -fID $$unique +tags: TAGS + +TAGS: $(HEADERS) $(SOURCES) $(TAGS_DEPENDENCIES) \ + $(TAGS_FILES) $(LISP) + set x; \ + here=`pwd`; \ + list='$(SOURCES) $(HEADERS) $(LISP) $(TAGS_FILES)'; \ + unique=`for i in $$list; do \ + if test -f "$$i"; then echo $$i; else echo $(srcdir)/$$i; fi; \ + done | \ + $(AWK) '{ files[$$0] = 1; nonempty = 1; } \ + END { if (nonempty) { for (i in files) print i; }; }'`; \ + shift; \ + if test -z "$(ETAGS_ARGS)$$*$$unique"; then :; else \ + test -n "$$unique" || unique=$$empty_fix; \ + if test $$# -gt 0; then \ + $(ETAGS) $(ETAGSFLAGS) $(AM_ETAGSFLAGS) $(ETAGS_ARGS) \ + "$$@" $$unique; \ + else \ + $(ETAGS) $(ETAGSFLAGS) $(AM_ETAGSFLAGS) $(ETAGS_ARGS) \ + $$unique; \ + fi; \ + fi +ctags: CTAGS +CTAGS: $(HEADERS) $(SOURCES) $(TAGS_DEPENDENCIES) \ + $(TAGS_FILES) $(LISP) + list='$(SOURCES) $(HEADERS) $(LISP) $(TAGS_FILES)'; \ + unique=`for i in $$list; do \ + if test -f "$$i"; then echo $$i; else echo $(srcdir)/$$i; fi; \ + done | \ + $(AWK) '{ files[$$0] = 1; nonempty = 1; } \ + END { if (nonempty) { for (i in files) print i; }; }'`; \ + test -z "$(CTAGS_ARGS)$$unique" \ + || $(CTAGS) $(CTAGSFLAGS) $(AM_CTAGSFLAGS) $(CTAGS_ARGS) \ + $$unique + +GTAGS: + here=`$(am__cd) $(top_builddir) && pwd` \ + && $(am__cd) $(top_srcdir) \ + && gtags -i $(GTAGS_ARGS) "$$here" + +distclean-tags: + -rm -f TAGS ID GTAGS GRTAGS GSYMS GPATH tags + +check-TESTS: $(TESTS) + @failed=0; all=0; xfail=0; xpass=0; skip=0; \ + srcdir=$(srcdir); export srcdir; \ + list=' $(TESTS) '; \ + $(am__tty_colors); \ + if test -n "$$list"; then \ + for tst in $$list; do \ + if test -f ./$$tst; then dir=./; \ + elif test -f $$tst; then dir=; \ + else dir="$(srcdir)/"; fi; \ + if $(TESTS_ENVIRONMENT) $${dir}$$tst; then \ + all=`expr $$all + 1`; \ + case " $(XFAIL_TESTS) " in \ + *[\ \ ]$$tst[\ \ ]*) \ + xpass=`expr $$xpass + 1`; \ + failed=`expr $$failed + 1`; \ + col=$$red; res=XPASS; \ + ;; \ + *) \ + col=$$grn; res=PASS; \ + ;; \ + esac; \ + elif test $$? -ne 77; then \ + all=`expr $$all + 1`; \ + case " $(XFAIL_TESTS) " in \ + *[\ \ ]$$tst[\ \ ]*) \ + xfail=`expr $$xfail + 1`; \ + col=$$lgn; res=XFAIL; \ + ;; \ + *) \ + failed=`expr $$failed + 1`; \ + col=$$red; res=FAIL; \ + ;; \ + esac; \ + else \ + skip=`expr $$skip + 1`; \ + col=$$blu; res=SKIP; \ + fi; \ + echo "$${col}$$res$${std}: $$tst"; \ + done; \ + if test "$$all" -eq 1; then \ + tests="test"; \ + All=""; \ + else \ + tests="tests"; \ + All="All "; \ + fi; \ + if test "$$failed" -eq 0; then \ + if test "$$xfail" -eq 0; then \ + banner="$$All$$all $$tests passed"; \ + else \ + if test "$$xfail" -eq 1; then failures=failure; else failures=failures; fi; \ + banner="$$All$$all $$tests behaved as expected ($$xfail expected $$failures)"; \ + fi; \ + else \ + if test "$$xpass" -eq 0; then \ + banner="$$failed of $$all $$tests failed"; \ + else \ + if test "$$xpass" -eq 1; then passes=pass; else passes=passes; fi; \ + banner="$$failed of $$all $$tests did not behave as expected ($$xpass unexpected $$passes)"; \ + fi; \ + fi; \ + dashes="$$banner"; \ + skipped=""; \ + if test "$$skip" -ne 0; then \ + if test "$$skip" -eq 1; then \ + skipped="($$skip test was not run)"; \ + else \ + skipped="($$skip tests were not run)"; \ + fi; \ + test `echo "$$skipped" | wc -c` -le `echo "$$banner" | wc -c` || \ + dashes="$$skipped"; \ + fi; \ + report=""; \ + if test "$$failed" -ne 0 && test -n "$(PACKAGE_BUGREPORT)"; then \ + report="Please report to $(PACKAGE_BUGREPORT)"; \ + test `echo "$$report" | wc -c` -le `echo "$$banner" | wc -c` || \ + dashes="$$report"; \ + fi; \ + dashes=`echo "$$dashes" | sed s/./=/g`; \ + if test "$$failed" -eq 0; then \ + echo "$$grn$$dashes"; \ + else \ + echo "$$red$$dashes"; \ + fi; \ + echo "$$banner"; \ + test -z "$$skipped" || echo "$$skipped"; \ + test -z "$$report" || echo "$$report"; \ + echo "$$dashes$$std"; \ + test "$$failed" -eq 0; \ + else :; fi + +distdir: $(DISTFILES) + @srcdirstrip=`echo "$(srcdir)" | sed 's/[].[^$$\\*]/\\\\&/g'`; \ + topsrcdirstrip=`echo "$(top_srcdir)" | sed 's/[].[^$$\\*]/\\\\&/g'`; \ + list='$(DISTFILES)'; \ + dist_files=`for file in $$list; do echo $$file; done | \ + sed -e "s|^$$srcdirstrip/||;t" \ + -e "s|^$$topsrcdirstrip/|$(top_builddir)/|;t"`; \ + case $$dist_files in \ + */*) $(MKDIR_P) `echo "$$dist_files" | \ + sed '/\//!d;s|^|$(distdir)/|;s,/[^/]*$$,,' | \ + sort -u` ;; \ + esac; \ + for file in $$dist_files; do \ + if test -f $$file || test -d $$file; then d=.; else d=$(srcdir); fi; \ + if test -d $$d/$$file; then \ + dir=`echo "/$$file" | sed -e 's,/[^/]*$$,,'`; \ + if test -d "$(distdir)/$$file"; then \ + find "$(distdir)/$$file" -type d ! -perm -700 -exec chmod u+rwx {} \;; \ + fi; \ + if test -d $(srcdir)/$$file && test $$d != $(srcdir); then \ + cp -fpR $(srcdir)/$$file "$(distdir)$$dir" || exit 1; \ + find "$(distdir)/$$file" -type d ! -perm -700 -exec chmod u+rwx {} \;; \ + fi; \ + cp -fpR $$d/$$file "$(distdir)$$dir" || exit 1; \ + else \ + test -f "$(distdir)/$$file" \ + || cp -p $$d/$$file "$(distdir)/$$file" \ + || exit 1; \ + fi; \ + done +check-am: all-am + $(MAKE) $(AM_MAKEFLAGS) $(check_PROGRAMS) + $(MAKE) $(AM_MAKEFLAGS) check-TESTS +check: check-am +all-am: Makefile $(LTLIBRARIES) +installdirs: + for dir in "$(DESTDIR)$(libdir)"; do \ + test -z "$$dir" || $(MKDIR_P) "$$dir"; \ + done +install: install-am +install-exec: install-exec-am +install-data: install-data-am +uninstall: uninstall-am + +install-am: all-am + @$(MAKE) $(AM_MAKEFLAGS) install-exec-am install-data-am + +installcheck: installcheck-am +install-strip: + $(MAKE) $(AM_MAKEFLAGS) INSTALL_PROGRAM="$(INSTALL_STRIP_PROGRAM)" \ + install_sh_PROGRAM="$(INSTALL_STRIP_PROGRAM)" INSTALL_STRIP_FLAG=-s \ + `test -z '$(STRIP)' || \ + echo "INSTALL_PROGRAM_ENV=STRIPPROG='$(STRIP)'"` install +mostlyclean-generic: + +clean-generic: + +distclean-generic: + -test -z "$(CONFIG_CLEAN_FILES)" || rm -f $(CONFIG_CLEAN_FILES) + -test . = "$(srcdir)" || test -z "$(CONFIG_CLEAN_VPATH_FILES)" || rm -f $(CONFIG_CLEAN_VPATH_FILES) + +maintainer-clean-generic: + @echo "This command is intended for maintainers to use" + @echo "it deletes files that may require special tools to rebuild." +clean: clean-am + +clean-am: clean-checkPROGRAMS clean-generic clean-libLTLIBRARIES \ + clean-libtool mostlyclean-am + +distclean: distclean-am + -rm -rf ./$(DEPDIR) + -rm -f Makefile +distclean-am: clean-am distclean-compile distclean-generic \ + distclean-tags + +dvi: dvi-am + +dvi-am: + +html: html-am + +html-am: + +info: info-am + +info-am: + +install-data-am: + +install-dvi: install-dvi-am + +install-dvi-am: + +install-exec-am: install-libLTLIBRARIES + +install-html: install-html-am + +install-html-am: + +install-info: install-info-am + +install-info-am: + +install-man: + +install-pdf: install-pdf-am + +install-pdf-am: + +install-ps: install-ps-am + +install-ps-am: + +installcheck-am: + +maintainer-clean: maintainer-clean-am + -rm -rf ./$(DEPDIR) + -rm -f Makefile +maintainer-clean-am: distclean-am maintainer-clean-generic + +mostlyclean: mostlyclean-am + +mostlyclean-am: mostlyclean-compile mostlyclean-generic \ + mostlyclean-libtool + +pdf: pdf-am + +pdf-am: + +ps: ps-am + +ps-am: + +uninstall-am: uninstall-libLTLIBRARIES + +.MAKE: check-am install-am install-strip + +.PHONY: CTAGS GTAGS all all-am check check-TESTS check-am clean \ + clean-checkPROGRAMS clean-generic clean-libLTLIBRARIES \ + clean-libtool ctags distclean distclean-compile \ + distclean-generic distclean-libtool distclean-tags distdir dvi \ + dvi-am html html-am info info-am install install-am \ + install-data install-data-am install-dvi install-dvi-am \ + install-exec install-exec-am install-html install-html-am \ + install-info install-info-am install-libLTLIBRARIES \ + install-man install-pdf install-pdf-am install-ps \ + install-ps-am install-strip installcheck installcheck-am \ + installdirs maintainer-clean maintainer-clean-generic \ + mostlyclean mostlyclean-compile mostlyclean-generic \ + mostlyclean-libtool pdf pdf-am ps ps-am tags uninstall \ + uninstall-am uninstall-libLTLIBRARIES + + +# Tell versions [3.59,3.63) of GNU make to not export all variables. +# Otherwise a system limit (for SysV at least) may be exceeded. +.NOEXPORT: diff --git a/src/fragmentation/defragmentation.c b/src/fragmentation/defragmentation.c new file mode 100644 index 0000000..b07f204 --- /dev/null +++ b/src/fragmentation/defragmentation.c @@ -0,0 +1,547 @@ +/* + This file is part of GNUnet + (C) 2009, 2011 Christian Grothoff (and other contributing authors) + + GNUnet is free software; you can redistribute it and/or modify + it under the terms of the GNU General Public License as published + by the Free Software Foundation; either version 3, or (at your + option) any later version. + + GNUnet is distributed in the hope that it will be useful, but + WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + General Public License for more details. + + You should have received a copy of the GNU General Public License + along with GNUnet; see the file COPYING. If not, write to the + Free Software Foundation, Inc., 59 Temple Place - Suite 330, + Boston, MA 02111-1307, USA. +*/ +/** + * @file src/fragmentation/defragmentation.c + * @brief library to help defragment messages + * @author Christian Grothoff + */ +#include "platform.h" +#include "gnunet_fragmentation_lib.h" +#include "fragmentation.h" + +/** + * Timestamps for fragments. + */ +struct FragTimes +{ + /** + * The time the fragment was received. + */ + struct GNUNET_TIME_Absolute time; + + /** + * Number of the bit for the fragment (in [0,..,63]). + */ + unsigned int bit; +}; + + +/** + * Information we keep for one message that is being assembled. Note + * that we keep the context around even after the assembly is done to + * handle 'stray' messages that are received 'late'. A message + * context is ONLY discarded when the queue gets too big. + */ +struct MessageContext +{ + /** + * This is a DLL. + */ + struct MessageContext *next; + + /** + * This is a DLL. + */ + struct MessageContext *prev; + + /** + * Associated defragmentation context. + */ + struct GNUNET_DEFRAGMENT_Context *dc; + + /** + * Pointer to the assembled message, allocated at the + * end of this struct. + */ + const struct GNUNET_MessageHeader *msg; + + /** + * Last time we received any update for this message + * (least-recently updated message will be discarded + * if we hit the queue size). + */ + struct GNUNET_TIME_Absolute last_update; + + /** + * Task scheduled for transmitting the next ACK to the + * other peer. + */ + GNUNET_SCHEDULER_TaskIdentifier ack_task; + + /** + * When did we receive which fragment? Used to calculate + * the time we should send the ACK. + */ + struct FragTimes frag_times[64]; + + /** + * Which fragments have we gotten yet? bits that are 1 + * indicate missing fragments. + */ + uint64_t bits; + + /** + * Unique ID for this message. + */ + uint32_t fragment_id; + + /** + * Which 'bit' did the last fragment we received correspond to? + */ + unsigned int last_bit; + + /** + * For the current ACK round, which is the first relevant + * offset in 'frag_times'? + */ + unsigned int frag_times_start_offset; + + /** + * Which offset whould we write the next frag value into + * in the 'frag_times' array? All smaller entries are valid. + */ + unsigned int frag_times_write_offset; + + /** + * Total size of the message that we are assembling. + */ + uint16_t total_size; + +}; + + +/** + * Defragmentation context (one per connection). + */ +struct GNUNET_DEFRAGMENT_Context +{ + + /** + * For statistics. + */ + struct GNUNET_STATISTICS_Handle *stats; + + /** + * Head of list of messages we're defragmenting. + */ + struct MessageContext *head; + + /** + * Tail of list of messages we're defragmenting. + */ + struct MessageContext *tail; + + /** + * Closure for 'proc' and 'ackp'. + */ + void *cls; + + /** + * Function to call with defragmented messages. + */ + GNUNET_FRAGMENT_MessageProcessor proc; + + /** + * Function to call with acknowledgements. + */ + GNUNET_DEFRAGMENT_AckProcessor ackp; + + /** + * Running average of the latency (delay between messages) for this + * connection. + */ + struct GNUNET_TIME_Relative latency; + + /** + * num_msgs how many fragmented messages + * to we defragment at most at the same time? + */ + unsigned int num_msgs; + + /** + * Current number of messages in the 'struct MessageContext' + * DLL (smaller or equal to 'num_msgs'). + */ + unsigned int list_size; + + /** + * Maximum message size for each fragment. + */ + uint16_t mtu; +}; + + +/** + * Create a defragmentation context. + * + * @param stats statistics context + * @param mtu the maximum message size for each fragment + * @param num_msgs how many fragmented messages + * to we defragment at most at the same time? + * @param cls closure for proc and ackp + * @param proc function to call with defragmented messages + * @param ackp function to call with acknowledgements (to send + * back to the other side) + * @return the defragmentation context + */ +struct GNUNET_DEFRAGMENT_Context * +GNUNET_DEFRAGMENT_context_create (struct GNUNET_STATISTICS_Handle *stats, + uint16_t mtu, unsigned int num_msgs, + void *cls, + GNUNET_FRAGMENT_MessageProcessor proc, + GNUNET_DEFRAGMENT_AckProcessor ackp) +{ + struct GNUNET_DEFRAGMENT_Context *dc; + + dc = GNUNET_malloc (sizeof (struct GNUNET_DEFRAGMENT_Context)); + dc->stats = stats; + dc->cls = cls; + dc->proc = proc; + dc->ackp = ackp; + dc->num_msgs = num_msgs; + dc->mtu = mtu; + dc->latency = GNUNET_TIME_UNIT_SECONDS; /* start with likely overestimate */ + return dc; +} + + +/** + * Destroy the given defragmentation context. + * + * @param dc defragmentation context + */ +void +GNUNET_DEFRAGMENT_context_destroy (struct GNUNET_DEFRAGMENT_Context *dc) +{ + struct MessageContext *mc; + + while (NULL != (mc = dc->head)) + { + GNUNET_CONTAINER_DLL_remove (dc->head, dc->tail, mc); + dc->list_size--; + if (GNUNET_SCHEDULER_NO_TASK != mc->ack_task) + { + GNUNET_SCHEDULER_cancel (mc->ack_task); + mc->ack_task = GNUNET_SCHEDULER_NO_TASK; + } + GNUNET_free (mc); + } + GNUNET_assert (0 == dc->list_size); + GNUNET_free (dc); +} + + +/** + * Send acknowledgement to the other peer now. + * + * @param cls the message context + * @param tc the scheduler context + */ +static void +send_ack (void *cls, const struct GNUNET_SCHEDULER_TaskContext *tc) +{ + struct MessageContext *mc = cls; + struct GNUNET_DEFRAGMENT_Context *dc = mc->dc; + struct FragmentAcknowledgement fa; + + mc->ack_task = GNUNET_SCHEDULER_NO_TASK; + fa.header.size = htons (sizeof (struct FragmentAcknowledgement)); + fa.header.type = htons (GNUNET_MESSAGE_TYPE_FRAGMENT_ACK); + fa.fragment_id = htonl (mc->fragment_id); + fa.bits = GNUNET_htonll (mc->bits); + GNUNET_STATISTICS_update (mc->dc->stats, + _("# acknowledgements sent for fragment"), 1, + GNUNET_NO); + dc->ackp (dc->cls, mc->fragment_id, &fa.header); +} + + +/** + * This function is from the GNU Scientific Library, linear/fit.c, + * (C) 2000 Brian Gough + */ +static void +gsl_fit_mul (const double *x, const size_t xstride, const double *y, + const size_t ystride, const size_t n, double *c1, double *cov_11, + double *sumsq) +{ + double m_x = 0, m_y = 0, m_dx2 = 0, m_dxdy = 0; + + size_t i; + + for (i = 0; i < n; i++) + { + m_x += (x[i * xstride] - m_x) / (i + 1.0); + m_y += (y[i * ystride] - m_y) / (i + 1.0); + } + + for (i = 0; i < n; i++) + { + const double dx = x[i * xstride] - m_x; + const double dy = y[i * ystride] - m_y; + + m_dx2 += (dx * dx - m_dx2) / (i + 1.0); + m_dxdy += (dx * dy - m_dxdy) / (i + 1.0); + } + + /* In terms of y = b x */ + + { + double s2 = 0, d2 = 0; + double b = (m_x * m_y + m_dxdy) / (m_x * m_x + m_dx2); + + *c1 = b; + + /* Compute chi^2 = \sum (y_i - b * x_i)^2 */ + + for (i = 0; i < n; i++) + { + const double dx = x[i * xstride] - m_x; + const double dy = y[i * ystride] - m_y; + const double d = (m_y - b * m_x) + dy - b * dx; + + d2 += d * d; + } + + s2 = d2 / (n - 1.0); /* chisq per degree of freedom */ + + *cov_11 = s2 * 1.0 / (n * (m_x * m_x + m_dx2)); + + *sumsq = d2; + } +} + + +/** + * Estimate the latency between messages based on the most recent + * message time stamps. + * + * @param mc context with time stamps + * @return average delay between time stamps (based on least-squares fit) + */ +static struct GNUNET_TIME_Relative +estimate_latency (struct MessageContext *mc) +{ + struct FragTimes *first; + size_t total = mc->frag_times_write_offset - mc->frag_times_start_offset; + double x[total]; + double y[total]; + size_t i; + double c1; + double cov11; + double sumsq; + struct GNUNET_TIME_Relative ret; + + first = &mc->frag_times[mc->frag_times_start_offset]; + GNUNET_assert (total > 1); + for (i = 0; i < total; i++) + { + x[i] = (double) i; + y[i] = (double) (first[i].time.abs_value - first[0].time.abs_value); + } + gsl_fit_mul (x, 1, y, 1, total, &c1, &cov11, &sumsq); + c1 += sqrt (sumsq); /* add 1 std dev */ + ret.rel_value = (uint64_t) c1; + if (ret.rel_value == 0) + ret = GNUNET_TIME_UNIT_MILLISECONDS; /* always at least 1 */ + return ret; +}; + + +/** + * Discard the message context that was inactive for the longest time. + * + * @param dc defragmentation context + */ +static void +discard_oldest_mc (struct GNUNET_DEFRAGMENT_Context *dc) +{ + struct MessageContext *old; + struct MessageContext *pos; + + old = NULL; + pos = dc->head; + while (NULL != pos) + { + if ((old == NULL) || + (old->last_update.abs_value > pos->last_update.abs_value)) + old = pos; + pos = pos->next; + } + GNUNET_assert (NULL != old); + GNUNET_CONTAINER_DLL_remove (dc->head, dc->tail, old); + dc->list_size--; + if (GNUNET_SCHEDULER_NO_TASK != old->ack_task) + { + GNUNET_SCHEDULER_cancel (old->ack_task); + old->ack_task = GNUNET_SCHEDULER_NO_TASK; + } + GNUNET_free (old); +} + + +/** + * We have received a fragment. Process it. + * + * @param dc the context + * @param msg the message that was received + * @return GNUNET_OK on success, GNUNET_NO if this was a duplicate, GNUNET_SYSERR on error + */ +int +GNUNET_DEFRAGMENT_process_fragment (struct GNUNET_DEFRAGMENT_Context *dc, + const struct GNUNET_MessageHeader *msg) +{ + struct MessageContext *mc; + const struct FragmentHeader *fh; + uint16_t msize; + uint16_t foff; + uint32_t fid; + char *mbuf; + unsigned int bit; + struct GNUNET_TIME_Absolute now; + struct GNUNET_TIME_Relative delay; + unsigned int bc; + unsigned int b; + unsigned int n; + int duplicate; + + if (ntohs (msg->size) < sizeof (struct FragmentHeader)) + { + GNUNET_break_op (0); + return GNUNET_SYSERR; + } + if (ntohs (msg->size) > dc->mtu) + { + GNUNET_break_op (0); + return GNUNET_SYSERR; + } + fh = (const struct FragmentHeader *) msg; + msize = ntohs (fh->total_size); + if (msize < sizeof (struct GNUNET_MessageHeader)) + { + GNUNET_break_op (0); + return GNUNET_SYSERR; + } + fid = ntohl (fh->fragment_id); + foff = ntohs (fh->offset); + if (foff >= msize) + { + GNUNET_break_op (0); + return GNUNET_SYSERR; + } + if (0 != (foff % (dc->mtu - sizeof (struct FragmentHeader)))) + { + GNUNET_break_op (0); + return GNUNET_SYSERR; + } + GNUNET_STATISTICS_update (dc->stats, _("# fragments received"), 1, GNUNET_NO); + mc = dc->head; + while ((NULL != mc) && (fid != mc->fragment_id)) + mc = mc->next; + bit = foff / (dc->mtu - sizeof (struct FragmentHeader)); + if (bit * (dc->mtu - sizeof (struct FragmentHeader)) + ntohs (msg->size) - + sizeof (struct FragmentHeader) > msize) + { + /* payload extends past total message size */ + GNUNET_break_op (0); + return GNUNET_SYSERR; + } + if ((NULL != mc) && (msize != mc->total_size)) + { + /* inconsistent message size */ + GNUNET_break_op (0); + return GNUNET_SYSERR; + } + now = GNUNET_TIME_absolute_get (); + if (NULL == mc) + { + mc = GNUNET_malloc (sizeof (struct MessageContext) + msize); + mc->msg = (const struct GNUNET_MessageHeader *) &mc[1]; + mc->dc = dc; + mc->total_size = msize; + mc->fragment_id = fid; + mc->last_update = now; + n = (msize + dc->mtu - sizeof (struct FragmentHeader) - 1) / (dc->mtu - + sizeof (struct + FragmentHeader)); + if (n == 64) + mc->bits = UINT64_MAX; /* set all 64 bit */ + else + mc->bits = (1LL << n) - 1; /* set lowest 'bits' bit */ + if (dc->list_size >= dc->num_msgs) + discard_oldest_mc (dc); + GNUNET_CONTAINER_DLL_insert (dc->head, dc->tail, mc); + dc->list_size++; + } + + /* copy data to 'mc' */ + if (0 != (mc->bits & (1LL << bit))) + { + mc->bits -= 1LL << bit; + mbuf = (char *) &mc[1]; + memcpy (&mbuf[bit * (dc->mtu - sizeof (struct FragmentHeader))], &fh[1], + ntohs (msg->size) - sizeof (struct FragmentHeader)); + mc->last_update = now; + if (bit < mc->last_bit) + mc->frag_times_start_offset = mc->frag_times_write_offset; + mc->last_bit = bit; + mc->frag_times[mc->frag_times_write_offset].time = now; + mc->frag_times[mc->frag_times_write_offset].bit = bit; + mc->frag_times_write_offset++; + duplicate = GNUNET_NO; + } + else + { + duplicate = GNUNET_YES; + GNUNET_STATISTICS_update (dc->stats, _("# duplicate fragments received"), 1, + GNUNET_NO); + } + + /* count number of missing fragments */ + bc = 0; + for (b = 0; b < 64; b++) + if (0 != (mc->bits & (1LL << b))) + bc++; + + /* notify about complete message */ + if ((duplicate == GNUNET_NO) && (0 == mc->bits)) + { + GNUNET_STATISTICS_update (dc->stats, _("# messages defragmented"), 1, + GNUNET_NO); + /* message complete, notify! */ + dc->proc (dc->cls, mc->msg); + } + /* send ACK */ + if (mc->frag_times_write_offset - mc->frag_times_start_offset > 1) + dc->latency = estimate_latency (mc); + delay = GNUNET_TIME_relative_multiply (dc->latency, bc + 1); + if ((0 == mc->bits) || (GNUNET_YES == duplicate)) /* message complete or duplicate, ACK now! */ + { + delay = GNUNET_TIME_UNIT_ZERO; + } + if (GNUNET_SCHEDULER_NO_TASK != mc->ack_task) + GNUNET_SCHEDULER_cancel (mc->ack_task); + mc->ack_task = GNUNET_SCHEDULER_add_delayed (delay, &send_ack, mc); + if (duplicate == GNUNET_YES) + return GNUNET_NO; + return GNUNET_YES; +} + +/* end of defragmentation.c */ diff --git a/src/fragmentation/fragmentation.c b/src/fragmentation/fragmentation.c new file mode 100644 index 0000000..8fab3fe --- /dev/null +++ b/src/fragmentation/fragmentation.c @@ -0,0 +1,405 @@ +/* + This file is part of GNUnet + (C) 2009, 2011 Christian Grothoff (and other contributing authors) + + GNUnet is free software; you can redistribute it and/or modify + it under the terms of the GNU General Public License as published + by the Free Software Foundation; either version 3, or (at your + option) any later version. + + GNUnet is distributed in the hope that it will be useful, but + WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + General Public License for more details. + + You should have received a copy of the GNU General Public License + along with GNUnet; see the file COPYING. If not, write to the + Free Software Foundation, Inc., 59 Temple Place - Suite 330, + Boston, MA 02111-1307, USA. +*/ +/** + * @file src/fragmentation/fragmentation.c + * @brief library to help fragment messages + * @author Christian Grothoff + */ +#include "platform.h" +#include "gnunet_fragmentation_lib.h" +#include "gnunet_protocols.h" +#include "fragmentation.h" + + +/** + * Fragmentation context. + */ +struct GNUNET_FRAGMENT_Context +{ + /** + * Statistics to use. + */ + struct GNUNET_STATISTICS_Handle *stats; + + /** + * Tracker for flow control. + */ + struct GNUNET_BANDWIDTH_Tracker *tracker; + + /** + * Current expected delay for ACKs. + */ + struct GNUNET_TIME_Relative delay; + + /** + * Next allowed transmission time. + */ + struct GNUNET_TIME_Absolute delay_until; + + /** + * Time we transmitted the last message of the last round. + */ + struct GNUNET_TIME_Absolute last_round; + + /** + * Message to fragment (allocated at the end of this struct). + */ + const struct GNUNET_MessageHeader *msg; + + /** + * Function to call for transmissions. + */ + GNUNET_FRAGMENT_MessageProcessor proc; + + /** + * Closure for 'proc'. + */ + void *proc_cls; + + /** + * Bitfield, set to 1 for each unacknowledged fragment. + */ + uint64_t acks; + + /** + * Bitfield with all possible bits for 'acks' (used to mask the + * ack we get back). + */ + uint64_t acks_mask; + + /** + * Task performing work for the fragmenter. + */ + GNUNET_SCHEDULER_TaskIdentifier task; + + /** + * Our fragmentation ID. (chosen at random) + */ + uint32_t fragment_id; + + /** + * Round-robin selector for the next transmission. + */ + unsigned int next_transmission; + + /** + * How many rounds of transmission have we completed so far? + */ + unsigned int num_rounds; + + /** + * GNUNET_YES if we called 'proc' and are now waiting for 'GNUNET_FRAGMENT_transmission_done' + */ + int8_t proc_busy; + + /** + * GNUNET_YES if we are waiting for an ACK. + */ + int8_t wack; + + /** + * Target fragment size. + */ + uint16_t mtu; + +}; + + +/** + * Transmit the next fragment to the other peer. + * + * @param cls the 'struct GNUNET_FRAGMENT_Context' + * @param tc scheduler context + */ +static void +transmit_next (void *cls, const struct GNUNET_SCHEDULER_TaskContext *tc) +{ + struct GNUNET_FRAGMENT_Context *fc = cls; + char msg[fc->mtu]; + const char *mbuf; + struct FragmentHeader *fh; + struct GNUNET_TIME_Relative delay; + unsigned int bit; + size_t size; + size_t fsize; + int wrap; + + fc->task = GNUNET_SCHEDULER_NO_TASK; + GNUNET_assert (GNUNET_NO == fc->proc_busy); + if (0 == fc->acks) + return; /* all done */ + + /* calculate delay */ + wrap = 0; + while (0 == (fc->acks & (1LL << fc->next_transmission))) + { + fc->next_transmission = (fc->next_transmission + 1) % 64; + wrap |= (fc->next_transmission == 0); + } + bit = fc->next_transmission; + size = ntohs (fc->msg->size); + if (bit == size / (fc->mtu - sizeof (struct FragmentHeader))) + fsize = + (size % (fc->mtu - sizeof (struct FragmentHeader))) + + sizeof (struct FragmentHeader); + else + fsize = fc->mtu; + if (fc->tracker != NULL) + delay = GNUNET_BANDWIDTH_tracker_get_delay (fc->tracker, fsize); + else + delay = GNUNET_TIME_UNIT_ZERO; + if (delay.rel_value > 0) + { + fc->task = GNUNET_SCHEDULER_add_delayed (delay, &transmit_next, fc); + return; + } + fc->next_transmission = (fc->next_transmission + 1) % 64; + wrap |= (fc->next_transmission == 0); + + /* assemble fragmentation message */ + mbuf = (const char *) &fc[1]; + fh = (struct FragmentHeader *) msg; + fh->header.size = htons (fsize); + fh->header.type = htons (GNUNET_MESSAGE_TYPE_FRAGMENT); + fh->fragment_id = htonl (fc->fragment_id); + fh->total_size = fc->msg->size; /* already in big-endian */ + fh->offset = htons ((fc->mtu - sizeof (struct FragmentHeader)) * bit); + memcpy (&fh[1], &mbuf[bit * (fc->mtu - sizeof (struct FragmentHeader))], + fsize - sizeof (struct FragmentHeader)); + if (NULL != fc->tracker) + GNUNET_BANDWIDTH_tracker_consume (fc->tracker, fsize); + GNUNET_STATISTICS_update (fc->stats, _("# fragments transmitted"), 1, + GNUNET_NO); + if (0 != fc->last_round.abs_value) + GNUNET_STATISTICS_update (fc->stats, _("# fragments retransmitted"), 1, + GNUNET_NO); + + /* select next message to calculate delay */ + bit = fc->next_transmission; + size = ntohs (fc->msg->size); + if (bit == size / (fc->mtu - sizeof (struct FragmentHeader))) + fsize = size % (fc->mtu - sizeof (struct FragmentHeader)); + else + fsize = fc->mtu; + if (NULL != fc->tracker) + delay = GNUNET_BANDWIDTH_tracker_get_delay (fc->tracker, fsize); + else + delay = GNUNET_TIME_UNIT_ZERO; + if (wrap) + { + /* full round transmitted wait 2x delay for ACK before going again */ + fc->num_rounds++; + delay = + GNUNET_TIME_relative_max (GNUNET_TIME_relative_multiply (delay, 2), + GNUNET_TIME_relative_multiply (fc->delay, + fc->num_rounds)); + /* never use zero, need some time for ACK always */ + delay = GNUNET_TIME_relative_max (GNUNET_TIME_UNIT_MILLISECONDS, delay); + fc->last_round = GNUNET_TIME_absolute_get (); + fc->wack = GNUNET_YES; + } + fc->proc_busy = GNUNET_YES; + fc->delay_until = GNUNET_TIME_relative_to_absolute (delay); + fc->proc (fc->proc_cls, &fh->header); +} + + +/** + * Create a fragmentation context for the given message. + * Fragments the message into fragments of size "mtu" or + * less. Calls 'proc' on each un-acknowledged fragment, + * using both the expected 'delay' between messages and + * acknowledgements and the given 'tracker' to guide the + * frequency of calls to 'proc'. + * + * @param stats statistics context + * @param mtu the maximum message size for each fragment + * @param tracker bandwidth tracker to use for flow control (can be NULL) + * @param delay expected delay between fragment transmission + * and ACK based on previous messages + * @param msg the message to fragment + * @param proc function to call for each fragment to transmit + * @param proc_cls closure for proc + * @return the fragmentation context + */ +struct GNUNET_FRAGMENT_Context * +GNUNET_FRAGMENT_context_create (struct GNUNET_STATISTICS_Handle *stats, + uint16_t mtu, + struct GNUNET_BANDWIDTH_Tracker *tracker, + struct GNUNET_TIME_Relative delay, + const struct GNUNET_MessageHeader *msg, + GNUNET_FRAGMENT_MessageProcessor proc, + void *proc_cls) +{ + struct GNUNET_FRAGMENT_Context *fc; + size_t size; + uint64_t bits; + + GNUNET_STATISTICS_update (stats, _("# messages fragmented"), 1, GNUNET_NO); + GNUNET_assert (mtu >= 1024 + sizeof (struct FragmentHeader)); + size = ntohs (msg->size); + GNUNET_STATISTICS_update (stats, _("# total size of fragmented messages"), + size, GNUNET_NO); + GNUNET_assert (size >= sizeof (struct GNUNET_MessageHeader)); + fc = GNUNET_malloc (sizeof (struct GNUNET_FRAGMENT_Context) + size); + fc->stats = stats; + fc->mtu = mtu; + fc->tracker = tracker; + fc->delay = delay; + fc->msg = (const struct GNUNET_MessageHeader *) &fc[1]; + fc->proc = proc; + fc->proc_cls = proc_cls; + fc->fragment_id = + GNUNET_CRYPTO_random_u32 (GNUNET_CRYPTO_QUALITY_WEAK, UINT32_MAX); + memcpy (&fc[1], msg, size); + bits = + (size + mtu - sizeof (struct FragmentHeader) - 1) / (mtu - + sizeof (struct + FragmentHeader)); + GNUNET_assert (bits <= 64); + if (bits == 64) + fc->acks_mask = UINT64_MAX; /* set all 64 bit */ + else + fc->acks_mask = (1LL << bits) - 1; /* set lowest 'bits' bit */ + fc->acks = fc->acks_mask; + fc->task = GNUNET_SCHEDULER_add_now (&transmit_next, fc); + return fc; +} + + +/** + * Continuation to call from the 'proc' function after the fragment + * has been transmitted (and hence the next fragment can now be + * given to proc). + * + * @param fc fragmentation context + */ +void +GNUNET_FRAGMENT_context_transmission_done (struct GNUNET_FRAGMENT_Context *fc) +{ + GNUNET_assert (fc->proc_busy == GNUNET_YES); + fc->proc_busy = GNUNET_NO; + GNUNET_assert (fc->task == GNUNET_SCHEDULER_NO_TASK); + fc->task = + GNUNET_SCHEDULER_add_delayed (GNUNET_TIME_absolute_get_remaining + (fc->delay_until), &transmit_next, fc); +} + + +/** + * Process an acknowledgement message we got from the other + * side (to control re-transmits). + * + * @param fc fragmentation context + * @param msg acknowledgement message we received + * @return GNUNET_OK if this ack completes the work of the 'fc' + * (all fragments have been received); + * GNUNET_NO if more messages are pending + * GNUNET_SYSERR if this ack is not valid for this fc + */ +int +GNUNET_FRAGMENT_process_ack (struct GNUNET_FRAGMENT_Context *fc, + const struct GNUNET_MessageHeader *msg) +{ + const struct FragmentAcknowledgement *fa; + uint64_t abits; + struct GNUNET_TIME_Relative ndelay; + + if (sizeof (struct FragmentAcknowledgement) != ntohs (msg->size)) + { + GNUNET_break_op (0); + return GNUNET_SYSERR; + } + fa = (const struct FragmentAcknowledgement *) msg; + if (ntohl (fa->fragment_id) != fc->fragment_id) + return GNUNET_SYSERR; /* not our ACK */ + abits = GNUNET_ntohll (fa->bits); + if ((GNUNET_YES == fc->wack) && (abits == (fc->acks & abits))) + { + /* normal ACK, can update running average of delay... */ + fc->wack = GNUNET_NO; + ndelay = GNUNET_TIME_absolute_get_duration (fc->last_round); + fc->delay.rel_value = + (ndelay.rel_value * fc->num_rounds + 3 * fc->delay.rel_value) / 4; + } + GNUNET_STATISTICS_update (fc->stats, + _("# fragment acknowledgements received"), 1, + GNUNET_NO); + if (abits != (fc->acks & abits)) + { + /* ID collission or message reordering, count! This should be rare! */ + GNUNET_STATISTICS_update (fc->stats, + _("# bits removed from fragmentation ACKs"), 1, + GNUNET_NO); + } + fc->acks = abits & fc->acks_mask; + if (0 != fc->acks) + { + /* more to transmit, do so right now (if tracker permits...) */ + if (fc->task != GNUNET_SCHEDULER_NO_TASK) + { + /* schedule next transmission now, no point in waiting... */ + GNUNET_SCHEDULER_cancel (fc->task); + fc->task = GNUNET_SCHEDULER_add_now (&transmit_next, fc); + } + else + { + /* only case where there is no task should be if we're waiting + * for the right to transmit again (proc_busy set to YES) */ + GNUNET_assert (GNUNET_YES == fc->proc_busy); + } + return GNUNET_NO; + } + + /* all done */ + GNUNET_STATISTICS_update (fc->stats, + _("# fragmentation transmissions completed"), 1, + GNUNET_NO); + if (fc->task != GNUNET_SCHEDULER_NO_TASK) + { + GNUNET_SCHEDULER_cancel (fc->task); + fc->task = GNUNET_SCHEDULER_NO_TASK; + } + return GNUNET_OK; +} + + +/** + * Destroy the given fragmentation context (stop calling 'proc', free + * resources). + * + * @param fc fragmentation context + * @return average delay between transmission and ACK for the + * last message, FOREVER if the message was not fully transmitted + */ +struct GNUNET_TIME_Relative +GNUNET_FRAGMENT_context_destroy (struct GNUNET_FRAGMENT_Context *fc) +{ + struct GNUNET_TIME_Relative ret; + + if (fc->task != GNUNET_SCHEDULER_NO_TASK) + GNUNET_SCHEDULER_cancel (fc->task); + ret = fc->delay; + GNUNET_free (fc); + return ret; +} + + +/* end of fragmentation.c */ diff --git a/src/fragmentation/fragmentation.h b/src/fragmentation/fragmentation.h new file mode 100644 index 0000000..2f3ea67 --- /dev/null +++ b/src/fragmentation/fragmentation.h @@ -0,0 +1,89 @@ +/* + This file is part of GNUnet + (C) 2009, 2011 Christian Grothoff (and other contributing authors) + + GNUnet is free software; you can redistribute it and/or modify + it under the terms of the GNU General Public License as published + by the Free Software Foundation; either version 3, or (at your + option) any later version. + + GNUnet is distributed in the hope that it will be useful, but + WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + General Public License for more details. + + You should have received a copy of the GNU General Public License + along with GNUnet; see the file COPYING. If not, write to the + Free Software Foundation, Inc., 59 Temple Place - Suite 330, + Boston, MA 02111-1307, USA. +*/ +/** + * @file src/fragmentation/fragmentation.h + * @brief library to help fragment messages + * @author Christian Grothoff + */ +#ifndef FRAGMENTATION_H +#define FRAGMENTATION_H +#include "platform.h" +#include "gnunet_fragmentation_lib.h" + +GNUNET_NETWORK_STRUCT_BEGIN + +/** + * Header for a message fragment. Followed by the + * original message. + */ +struct FragmentHeader +{ + + /** + * Message header. + */ + struct GNUNET_MessageHeader header; + + /** + * Unique fragment ID. + */ + uint32_t fragment_id; + + /** + * Total message size of the original message. + */ + uint16_t total_size; + + /** + * Absolute offset (in bytes) of this fragment in the original + * message. Will be a multiple of the MTU. + */ + uint16_t offset; + +}; + + +/** + * Message fragment acknowledgement. + */ +struct FragmentAcknowledgement +{ + + /** + * Message header. + */ + struct GNUNET_MessageHeader header; + + /** + * Unique fragment ID. + */ + uint32_t fragment_id; + + /** + * Bits that are being acknowledged, in big-endian. + * (bits that are set correspond to fragments that + * have not yet been received). + */ + uint64_t bits; + +}; +GNUNET_NETWORK_STRUCT_END + +#endif diff --git a/src/fragmentation/test_fragmentation.c b/src/fragmentation/test_fragmentation.c new file mode 100644 index 0000000..c409bf3 --- /dev/null +++ b/src/fragmentation/test_fragmentation.c @@ -0,0 +1,261 @@ +/* + This file is part of GNUnet + (C) 2004, 2009 Christian Grothoff (and other contributing authors) + + GNUnet is free software; you can redistribute it and/or modify + it under the terms of the GNU General Public License as published + by the Free Software Foundation; either version 3, or (at your + option) any later version. + + GNUnet is distributed in the hope that it will be useful, but + WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + General Public License for more details. + + You should have received a copy of the GNU General Public License + along with GNUnet; see the file COPYING. If not, write to the + Free Software Foundation, Inc., 59 Temple Place - Suite 330, + Boston, MA 02111-1307, USA. +*/ +/** + * @file fragmentation/test_fragmentation.c + * @brief test for fragmentation.c + * @author Christian Grothoff + */ +#include "platform.h" +#include "gnunet_fragmentation_lib.h" + +#define VERBOSE GNUNET_NO + +#define DETAILS GNUNET_NO + +/** + * Number of messages to transmit (note: each uses ~32k memory!) + */ +#define NUM_MSGS 5000 + +/** + * MTU to force on fragmentation (must be > 1k + 12) + */ +#define MTU 1111 + +/** + * Simulate dropping of 1 out of how many messages? (must be > 1) + */ +#define DROPRATE 10 + +static int ret = 1; + +static unsigned int dups; + +static unsigned int fragc; + +static unsigned int frag_drops; + +static unsigned int acks; + +static unsigned int ack_drops; + +static struct GNUNET_DEFRAGMENT_Context *defrag; + +static struct GNUNET_BANDWIDTH_Tracker trackers[NUM_MSGS]; + +static struct GNUNET_FRAGMENT_Context *frags[NUM_MSGS]; + +static GNUNET_SCHEDULER_TaskIdentifier shutdown_task; + +static void +do_shutdown (void *cls, const struct GNUNET_SCHEDULER_TaskContext *tc) +{ + unsigned int i; + + ret = 0; + shutdown_task = GNUNET_SCHEDULER_NO_TASK; + GNUNET_DEFRAGMENT_context_destroy (defrag); + defrag = NULL; + for (i = 0; i < NUM_MSGS; i++) + { + if (frags[i] == NULL) + continue; + GNUNET_FRAGMENT_context_destroy (frags[i]); + frags[i] = NULL; + } +} + + +static void +proc_msgs (void *cls, const struct GNUNET_MessageHeader *hdr) +{ + static unsigned int total; + unsigned int i; + const char *buf; + +#if DETAILS + FPRINTF (stderr, "%s", "!"); /* message complete, good! */ +#endif + buf = (const char *) hdr; + for (i = sizeof (struct GNUNET_MessageHeader); i < ntohs (hdr->size); i++) + GNUNET_assert (buf[i] == (char) i); + total++; +#if ! DETAILS + if (0 == (total % (NUM_MSGS / 100))) + FPRINTF (stderr, "%s", "."); +#endif + /* tolerate 10% loss, i.e. due to duplicate fragment IDs */ + if ((total >= NUM_MSGS - (NUM_MSGS / 10)) && (ret != 0)) + { + if (GNUNET_SCHEDULER_NO_TASK == shutdown_task) + shutdown_task = GNUNET_SCHEDULER_add_now (&do_shutdown, NULL); + } +} + + +/** + * Process ACK (by passing to fragmenter) + */ +static void +proc_acks (void *cls, uint32_t msg_id, const struct GNUNET_MessageHeader *hdr) +{ + unsigned int i; + int ret; + + if (0 == GNUNET_CRYPTO_random_u32 (GNUNET_CRYPTO_QUALITY_WEAK, DROPRATE)) + { + ack_drops++; + return; /* random drop */ + } + for (i = 0; i < NUM_MSGS; i++) + { + if (frags[i] == NULL) + continue; + ret = GNUNET_FRAGMENT_process_ack (frags[i], hdr); + if (ret == GNUNET_OK) + { +#if DETAILS + FPRINTF (stderr, "%s", "@"); /* good ACK */ +#endif + GNUNET_FRAGMENT_context_destroy (frags[i]); + frags[i] = NULL; + acks++; + return; + } + if (ret == GNUNET_NO) + { +#if DETAILS + FPRINTF (stderr, "%s", "@"); /* good ACK */ +#endif + acks++; + return; + } + } +#if DETAILS + FPRINTF (stderr, "%s", "_"); /* BAD: ack that nobody feels responsible for... */ +#endif +} + + +/** + * Process fragment (by passing to defrag). + */ +static void +proc_frac (void *cls, const struct GNUNET_MessageHeader *hdr) +{ + struct GNUNET_FRAGMENT_Context **fc = cls; + int ret; + + GNUNET_FRAGMENT_context_transmission_done (*fc); + if (0 == GNUNET_CRYPTO_random_u32 (GNUNET_CRYPTO_QUALITY_WEAK, DROPRATE)) + { + frag_drops++; + return; /* random drop */ + } + if (NULL == defrag) + { + FPRINTF (stderr, "%s", "E"); /* Error: frag after shutdown!? */ + return; + } + ret = GNUNET_DEFRAGMENT_process_fragment (defrag, hdr); + if (ret == GNUNET_NO) + { +#if DETAILS + FPRINTF (stderr, "%s", "?"); /* duplicate fragment */ +#endif + dups++; + } + else if (ret == GNUNET_OK) + { +#if DETAILS + FPRINTF (stderr, "%s", "."); /* good fragment */ +#endif + fragc++; + } +} + + +/** + * Main function run with scheduler. + */ +static void +run (void *cls, char *const *args, const char *cfgfile, + const struct GNUNET_CONFIGURATION_Handle *cfg) +{ + unsigned int i; + struct GNUNET_MessageHeader *msg; + char buf[MTU + 32 * 1024]; + + defrag = GNUNET_DEFRAGMENT_context_create (NULL, MTU, NUM_MSGS /* enough space for all */ + , NULL, &proc_msgs, &proc_acks); + for (i = 0; i < sizeof (buf); i++) + buf[i] = (char) i; + msg = (struct GNUNET_MessageHeader *) buf; + for (i = 0; i < NUM_MSGS; i++) + { + msg->type = htons ((uint16_t) i); + msg->size = + htons (sizeof (struct GNUNET_MessageHeader) + (17 * i) % (32 * 1024)); + frags[i] = GNUNET_FRAGMENT_context_create (NULL /* no stats */ , + MTU, &trackers[i], + GNUNET_TIME_UNIT_SECONDS, msg, + &proc_frac, &frags[i]); + } +} + + +int +main (int argc, char *argv[]) +{ + struct GNUNET_GETOPT_CommandLineOption options[] = { + GNUNET_GETOPT_OPTION_END + }; + char *const argv_prog[] = { + "test-fragmentation", + "-c", + "test_fragmentation_data.conf", + "-L", +#if VERBOSE + "DEBUG", +#else + "WARNING", +#endif + NULL + }; + unsigned int i; + + GNUNET_log_setup ("test-fragmentation", +#if VERBOSE + "DEBUG", +#else + "WARNING", +#endif + NULL); + for (i = 0; i < NUM_MSGS; i++) + GNUNET_BANDWIDTH_tracker_init (&trackers[i], + GNUNET_BANDWIDTH_value_init ((i + 1) * 1024), + 100); + GNUNET_PROGRAM_run (5, argv_prog, "test-fragmentation", "nohelp", options, + &run, NULL); + FPRINTF (stderr, + "\nHad %u good fragments, %u duplicate fragments, %u acks and %u simulated drops of acks\n", + fragc, dups, acks, ack_drops); + return ret; +} diff --git a/src/fragmentation/test_fragmentation_data.conf b/src/fragmentation/test_fragmentation_data.conf new file mode 100644 index 0000000..c236f68 --- /dev/null +++ b/src/fragmentation/test_fragmentation_data.conf @@ -0,0 +1,5 @@ + +[nse] +AUTOSTART = NO + + |