The reason is some people are blocked to access git:// protocol/port
because of firewall setup in their environment, and git.ozlabs.org does
not provide a way to clone over http(s).

We can provide CCAN mirror and we support cloning it over http(s). Also,
it makes sense to not depend on thirdparty sites for hosting
strongly-related components.

We currently use subprocess.check_output() for running external command
(git), and check_output() checks running command status code, as its
name promises:

    https://github.com/python/cpython/blob/2.7/Lib/subprocess.py#L569

and reports it appropriately to user:

    https://github.com/python/cpython/blob/2.7/Lib/subprocess.py#L411

but if the command is not found, it is just single

    error: [Errno 2] No such file or directory

which gets output to the log and it is not clear what command failed, or
evern if it is from runcmd() call.

Redo our runcmd() manually, so that it always report erros with context
- what command it was trying to run. The error now becomes:

   RuntimeError: (['missing-command'],): [Errno 2] No such file or directory

/cc @Tyagov

If setuptools.file_finders group is not registered,
dist.get_entry_map('setuptools.file_finders') returns just {} not
connected to entry map, and further modifications of this dict go
nowhere (and thus, our git_lsfiles() is not hooked -> sdist fails to
produce correct source archive).

This is a workaround for setuptools 9.0 dropping
`setuptools.file_finders` entrypoint group registration:

    https://bitbucket.org/pypa/setuptools/commits/f191c8a1225bd58a5fb5aa9abb31b06dc710f0b9#Lsetup.pyF175
    https://bitbucket.org/pypa/setuptools/issue/313

issue reported back:

    https://bitbucket.org/pypa/setuptools/issue/313#comment-18430008

It was hanging with NumPy-1.9 before 425dc5d1 (bigarray: Raise
IndexError for out-of-bound element access), because of the following
correct NumPy commit:

    https://github.com/numpy/numpy/commit/d36f8227

and in particular

    https://github.com/numpy/numpy/commit/d36f8227#diff-6d326badc0872de91e025cbfb0be1aafR522

That PySequence_Fast(obj)    (with obj being BigArray)

creates iterator on top of obj and before our previous IndexError fix in
425dc5d1, this was looping forever.

Test explicitly with both NumPy 1.8 and NumPy 1.9, that this construct
does not hang.

/cc @Tyagov

The way BigArray.__getitem__ works for element access is that for e.g.

    A[i]

it translates the request to

    A[i:i+1]

and remembers to lower the dimensionality at scalar index

    dim_adjust = (0,)

so, in full, A[i] is computed this way:

    A[i] -> A[i:i+1](0,)

( it is done this way to unify code for scalar / slice access in
  __getitem__ - see 0c826d5c "BigArray: An ndarray-like on top of
  BigFile memory mappings" )

The code for slice access also has a shortcut - if it sees that slice
results in empty array (e.g. for out-of-bound slice), we can avoid
spending time to create a file vma mapping only to create empty view on
top of it.

In 0c826d5c, that optimization, however forgot to apply the "lower the
dimensionality" step on top of resulting empty view, and that turned out
for not raising IndexError for out-of-bounds scalar access:

    A = BigArray((10,), uint8)
    In [1]: A[0]
    Out[1]: 0

    In [2]: A[1]
    Out[2]: 0

    In [3]: A[2]
    Out[3]: 0

    In [4]: A[9]
    Out[4]: 0

    In [5]: A[10]
    Out[5]: array([], dtype=uint8)

NOTE that A[10] returns empty array instead of raising IndexError.

So do not forget to apply the "reduce dimensionality" step for empty
views, and this way we get proper IndexError (because for empty view,
scalar access results in IndexError).

NOTE:

this bug was also preventing for e.g.

    list(A)

to work, because list(A) internally works this way:

    l = []
    i = iter(A)
    for _ in i:
        l.append(_)

but iterating would not stop after 10 elements - after array end, _ will
be always array([], dtype=uint8), and thus the loop never finished and
memory usage grow to infinity.

/cc @Tyagov

In NumPy speak advanced indexing is picking up arbitrarily requested
elemtnts, e.g.

    a = arange(10)
    a[[0,3,2]]  -> array([0, 3, 2])

The way this indexing schem works is - it creates a new array with
len = len(key), and picks up requested elements sequentially into new
area.

So it is very not the same as creating _view_ to original array data by
using basic indexing [1]

BigArray does not support advanced indexing, because its main job is to
organize an ndarray _view_ backed up by BigFile data and give that view
to clients, and then it is up to clients how to use that view with full
numpy api available with it.

So be explicit, and reject advanced indexing in __getitem__ right at the
beginning.

[1] http://docs.scipy.org/doc/numpy/reference/arrays.indexing.html

Else, in a clean repo the tests do not build from scratch:

    $ make test
    x86_64-linux-gnu-gcc -pthread -g -Wall -D_GNU_SOURCE -std=gnu99 -fplan9-extensions -Wno-declaration-after-statement -Wno-error=declaration-after-statement  -Iinclude -I3rdparty/ccan -I3rdparty/include   bigfile/tests/test_virtmem.c lib/bug.c lib/utils.c 3rdparty/ccan/ccan/tap/tap.c  -o bigfile/tests/test_virtmem.t
    In file included from include/wendelin/list.h:11:0,
                     from include/wendelin/bigfile/virtmem.h:33,
                     from bigfile/tests/../virtmem.c:23,
                     from bigfile/tests/test_virtmem.c:21:
    3rdparty/ccan/ccan/array_size/array_size.h:4:20: fatal error: config.h: No such file or directory
     #include "config.h"
                        ^
    compilation terminated.
    3rdparty/ccan/ccan/tap/tap.c:26:20: fatal error: config.h: No such file or directory
     #include "config.h"
                        ^
    compilation terminated.
    Makefile:99: recipe for target 'bigfile/tests/test_virtmem.t' failed
    make: *** [bigfile/tests/test_virtmem.t] Error 1

In NumPy, ndarray has .resize() but actually it does a whole array
copy into newly allocated larger segment which makes e.g. appending O(n).

For BigArray, we don't have that internal constraint NumPy has - to
keep the array itself contiguously _stored_ (compare to contiguously
_presented_ in memory). So we can have O(1) resize for big arrays.

NOTE having O(1) resize, here is how O(δ) append can be done:

    A                               # ZBigArray e.g. of shape   (N, 3)
    n = len(A)                      # lengh of A's major index  =N
    A.resize((n+δ, A.shape[1:]))    # add δ new entries ; now len(A) =N+δ
    A[-δ:] = <new-data>             # set data for last new δ entries

/cc @klaus

test_bigarray_indexing_Nd() contains useful class to have a BigFile
connected to ndarray storage. Factor it out so that all tests could use
it.

BigFile_Data.storeblk() is newly introduced and is currently unused, but
will be convenient to have later.

In 5755a6b3 (Basic setup.py / Makefile to build/install/sdist stuff +
bigfile.so skeleton) we overlooked one thing:

    when tailing from setup.py to make level, we forgot to setup the
    PYTHON env variable properly, and that leads to changing building
    with std python.

Look e.g.

    $ python3 setup.py build_ext -i
    running build_ext
    python setup.py ll_build_ext --inplace
    ^^^

which is obviously not correct.

Fix it.

The tox setup we have setup for testing with multiple interpreters
(7af2b2d7 "Tox setup to test things with py27 & py34 and several
versions of ZODB") did not caught this, because for every python and
environment versions tox initializes separate virtualenv, in which
.../bin/python is a link to chosen python, and this way both python and
my-selected-for-build-python are the same.

Cc: @Tyagov

For example on Debian 7 Wheezy the kernel (linux 3.2) supports holepunching,
because holepunching was added in linux 2.6.38:

    http://git.kernel.org/linus/79124f18b335172e1916075c633745e12dae1dac

but glibc does not provide fallocate mode constants, and compilation fails:

    gcc -pthread -fno-strict-aliasing -g -O2 -DNDEBUG -g -fwrapv -O3 -Wall -Wstrict-prototypes -fPIC -D_GNU_SOURCE -I./include -I./3rdparty/ccan -I./3rdparty/include -I/opt/slapgrid/f2a5f59d0d2b521681b9333ee76a2859/parts/python2.7/include/python2.7 -c bigfile/ram_shmfs.c -o build/temp.linux-x86_64-2.7/bigfile/ram_shmfs.o -std=gnu99 -fplan9-extensions -fvisibility=hidden -Wno-declaration-after-statement -Wno-error=declaration-after-statement
    bigfile/ram_shmfs.c: In function ‘shmfs_drop_memory’:
    bigfile/ram_shmfs.c:135:31: error: ‘FALLOC_FL_PUNCH_HOLE’ undeclared (first use in this function)
    bigfile/ram_shmfs.c:135:31: note: each undeclared identifier is reported only once for each function it appears in
    bigfile/ram_shmfs.c:135:54: error: ‘FALLOC_FL_KEEP_SIZE’ undeclared (first use in this function)
    error: command 'gcc' failed with exit status 1

Try to fix it via fallbacking to provide the needed defines on older systems ourselves.

Cc: Klaus Wölfel <klaus@nexedi.com>
Cc: Ivan Tyagov <ivan@tyagov.com>

In C99 declaration after statement is ok, and we explicitly compile with -std=gnu99.

Python >= 3.4 however adds -Werror=declaration-after-statement even for extension
modules irregardless of their compilation flags:

  https://bugs.python.org/issue21121

and the build fails this way:

    building 'wendelin.bigfile._bigfile' extension
    creating build/temp.linux-x86_64-3.4
    creating build/temp.linux-x86_64-3.4/bigfile
    creating build/temp.linux-x86_64-3.4/lib
    gcc -pthread -Wno-unused-result -Werror=declaration-after-statement -DNDEBUG -fmessage-length=0 -grecord-gcc-switches -O2 -Wall
-D_FORTIFY_SOURCE=2 -fstack-protector -funwind-tables -fasynchronous-unwind-tables -g -DOPENSSL_LOAD_CONF -fPIC -D_GNU_SOURCE
-I./include -I./3rdparty/ccan -I./3rdparty/include -I/usr/include/python3.4m -c bigfile/_bigfile.c -o build/temp.linux-x86_64-3.4/bigfile/_bigfile.o
-std=gnu99 -fplan9-extensions -fvisibility=hidden
    bigfile/_bigfile.c: In function ‘pyfile_new’:
    bigfile/_bigfile.c:679:5: error: ISO C90 forbids mixed declarations and code [-Werror=declaration-after-statement]
         static char *kw_list[] = {"blksize", NULL};
         ^
    cc1: some warnings being treated as errors
    error: command 'gcc' failed with exit status 1

Ensure we turn off this warning and error because we already rely on compiling in C99 mode.
Reported-and-tested-by: Ivan Tyagov <ivan@tyagov.com>

This shows how to first generate such arrays (in steps, as every
transaction change should fit in memory), and then gather data from
whole array using C/Fortran/etc code.

It shows how to compute mean via NumPy's ndarray.mean()

It also shows that e.g. ndarray.var() wants to create temporaries in
size of original ndarray and that would fail, because it does not fit
into RAM.

ndarray.var() should not need to create such temporaries in principle -
all it has to do is to first compute mean, and then compute

    sum (Xi - <X>)^2

in a loop.

<X> is scalar, Xi - is just access to original array.

~~~~

So this also show NumPy can be incrementally improved to avoid creating
such temporaries, and then it will work.

    - for virtual memory subsytem
    - for ZBigFiles

They are not currently great, e.g. for virtmem we have in-kernel
overhead of page clearing - in perf profiles, for bigfile_mmap compared
to file_read kernel's clear_page_c raises significantly.

That is the worker for clearing page memory and we currently cannot
avoid that - any memory obtained from kernel (MAP_ANONYMOUS, mmap(file)
with hole, etc...) comes pre-initialized to zeros to userspace.

This can be seen in the benchmarks as well: file_readbig differs from
file_read in only that the latter uses 1 small buffer and the first
allocates large memory (cleared by kernel + python does the memset).

    bigfile/tests/bench_virtmem.py@125::bench_file_mmap_adler32     0.47  (0.86 0.49 0.47)
    bigfile/tests/bench_virtmem.py@126::bench_file_read_adler32     0.69  (1.11 0.71 0.69)
    bigfile/tests/bench_virtmem.py@127::bench_file_readbig_adler32  1.41  (1.70 1.42 1.41)
    bigfile/tests/bench_virtmem.py@128::bench_bigfile_mmap_adler32  1.42  (1.45 1.42 1.51)

    bigfile/tests/bench_virtmem.py@130::bench_file_mmap_md5         1.52  (1.91 1.54 1.52)
    bigfile/tests/bench_virtmem.py@131::bench_file_read_md5         1.73  (2.10 1.75 1.73)
    bigfile/tests/bench_virtmem.py@132::bench_file_readbig_md5      2.44  (2.73 2.46 2.44)
    bigfile/tests/bench_virtmem.py@133::bench_bigfile_mmap_md5      2.40  (2.48 2.40 2.53)

There is MAP_UNINITIALIZED which works only for non-mmu targets and only
if explicitly allowed when configuring kernel (off by default).

There were patches to disable that pages zeroing, as it gives
significant speedup for people's workloads, e.g. [1,2] but all of them
did not got merged for security reasons.

[1] http://marc.info/?t=132691315900001&r=1&w=2
[2] http://thread.gmane.org/gmane.linux.kernel/548926

~~~~

For ZBigFile - it is the storage who is dominating in profiles.

For this, a small wrapper over py.test is developed (to discover/collect
functions to benchmar, etc) and then it runs such functions several
times in a boxed enveronment.

Benchmarks should be named bench_*.py

This is like to BigArray, like ZBigFile is to BigFile (4174b84a
"bigfile: BigFile backend to store data in ZODB")

I.e. something like numpy.memmap for numpy.ndarray and OS files. The whole
bigarray cannot be used as a drop-in replacement for numpy arrays, but BigArray
_slices_ are real ndarrays and can be used everywhere ndarray can be used,
including in C/Fortran code. Slice size is limited by mapping-size (=
address-space size) limit, i.e. to ~ max 127TB on Linux/amd64.

Changes to bigarray memory are changes to bigfile memory mapping and as such
can be discarded or saved back to bigfile using mapping (= BigFileH) dirty
discard/writeout interface.

For the same reason the whole amount of changes to memory is limited by amount
of physical RAM.

This adds transactionality and with e.g. NEO[1] allows to distribute
objects to nodes into cluster.

We hook into ZODB two-phase commit process as a separate data manager,
and synchronize changes to memory, to changes to object only at that
time.

Alternative would be to get notified on every page change, and mark
appropriate object as dirty right at that moment.

But I wanted to stay close to filesystem design (we don't get
notification for every file change from kernel) - that's why it is done
the first way.

[1] http://www.neoppod.org/

In Python. To demonstrate how backends could be implemented and test
system on simple things.

Exposes BigFile - this way users can define BigFile backend in Python.

Also exposed are BigFile handles, and VMA objects which are results of
mmaping.

We'll use py.test for unit-testing of Python part.

Does similar things to what kernel does - users can mmap file parts into
address space and access them read/write. The manager will be getting
invoked by hardware/OS kernel for cases when there is no page loaded for
read, or when a previousle read-only page is being written to.

Additionally to features provided in kernel, it support to be used to
store back changes in transactional way (see fileh_dirty_writeout()) and
potentially use huge pages for mappings (though this is currently TODO)

Users can inherit from BigFile and provide custom ->loadblk() and
->storeblk() to load/store file blocks from a database or some other
storage. The system then could use such files to memory map them into
user address space (see next patch).

Useful to debug (via either printk or gdb) the kernel - one can boot it,
and tweak compile test program on host and be ready to test it inside
qemu on tested kernel. Another use case is to add tracing printk to
kernel and to boot it on each iteration. Booting via qemu means the
workflow is not disrupted as would with rebooting the hardware.

With this tool it was straightforward to find out why mmap-alias through
mremap does not work for huge pages:

static struct vm_area_struct *vma_to_resize(unsigned long addr,
        unsigned long old_len, unsigned long new_len, unsigned long *p)
{
        struct mm_struct *mm = current->mm;
        struct vm_area_struct *vma = find_vma(mm, addr);

        if (!vma || vma->vm_start > addr)
                goto Efault;

        if (is_vm_hugetlb_page(vma))            <--
                goto Einval;

mremap_to(...)
{
        /* lots of checks, then */
        vma_to_resize(...)

This thing allows to get aliasable RAM from OS kernel and to manage it.
Currently we get memory from a tmpfs mount, and hugetlbfs should also
work, but is TODO because hugetlbfs in the kernel needs to be improved.

We need aliasing because we'll need to be able to memory map the same
page into several places in address space, e.g. for taking two slices
overlapping slice of the same array at different times.

Comes with test programs that show we aliasing does not work for
anonymous memory.

This will be the core of virtual memory subsystem. For now we just
define a structure to describe pages of memory and add utility to
allocate address space from OS.

We hook into SIGSEGV and handle read/write pagefaults this way.

In this patch there goes stub code that only detects faults and
determines (in arch specific way) whether fault was for read or write
and there is a TODO to pass that information to higher level.

It also comes with tests to detect we still crash if we access something
incorrectly, so people could have coredumps and investigate them.

For BigFiles we'll needs to maintain `{} offset-in-file -> void *` mapping. A
hash or a binary tree could be used there, but since we know files are
most of the time accessed sequentially and locally in pages-batches, we
can also organize the mapping in batches of keys.

Specifically offset bits are so divided into parts, that every part
addresses 1 entry in a table of hardware-page in size. To get to the actual
value, the system lookups first table by first part of offset, then from
first table and next part from address - second table, etc.

To clients this looks like a dictionary with get/set/del & clear methods,
but lookups are O(1) time always, and in contrast to hashes values are
stored with locality (= adjacent lookups almost always access the same tables).

We'll be testing C code in a similiar-to-python way - keep test_*.c
files nearby and compile/executing them as needed.

Tests are run several times in several ways - as plainly compiled and
also with additional error checkers:

 - AddressSanitizer
 - ThreadSanitizer
 - and similiar checkers from Valgrind