loadblk() calls are potentially slow and external code that serve the cal can
take other locks in addition to virtmem lock taken by virtmem subsystem. If
that "other locks" are also taken before external code calls e.g.
fileh_invalidate_page() in different codepath a deadlock can happen, e.g.

      T1                  T2

      page-access         invalidation-from-server received
      V -> loadblk
                          Z   <- ClientStorage.invalidateTransaction()
      Z -> zeo.load
                          V   <- fileh_invalidate_page

The solution to avoid deadlock is to call loadblk() with virtmem lock released
and upon loadblk() completion recheck virtmem data structures carefully.

To make that happen:

- new page state is introduces:

    PAGE_LOADING                (file content loading is  in progress)

- virtmem releases virt_lock before calling loadblk() when serving pagefault

- because loading is now done with virtmem lock released, now:

1. After loading completes we need to recheck fileh/vma data structures

   The recheck is done in full - vma_on_pagefault() just asks its driver (see
   VM_RETRY and VM_HANDLED codes) to retry handling the fault completely. This
   should work as the freshly loaded page was just inserted into fileh->pagemap
   and should be found there in the cache on next lookup.

   On the other hand this also works correctly, if there was concurrent change
   - e.g. vma was unmapped while we were loading the data - in that case the
   fault will be also processed correctly - but loaded data will stay in
   fileh->pagemap (and if not used will be evicted as not-needed
   eventually by RAM reclaim).

2. Similar to retrying mechanism is used for cases when two threads
   concurrently access the same page and would both try to load corresponding
   block - only one thread issues the actual loadblk() and another waits for load
   to complete with polling and VM_RETRY.

3. To correctly invalidate loading-in-progress pages another new page state
   is introduced:

    PAGE_LOADING_INVALIDATED    (file content loading was in progress
                                 while request to invalidate the page came in)

   which fileh_invalidate_page() uses to propagate invalidation message to
   loadblk() caller.

4. Blocks loading can now happen in parallel with other block loading and
   other virtmem operations - e.g. invalidation. For such cases tests are added
   to test_thread.py

5. virtmem lock now becomes just regular lock, instead of being previously
   recursive.

   For virtmem lock to be recursive was needed for cases, when code under
   loadblk() could trigger other virtmem calls, e.g. due to GC and calling
   another VMA dtor that would want to lock virtmem, but virtmem lock was
   already held.

   This is no longer needed.

6. To catch double faults we now cannot use just on static variable
   in_on_pagefault. That variable thus becomes thread-local.

7. Old test in test_thread to "test that access vs access don't overlap" no
   longer holds true - and is thus removed.

/cc @Tyagov, @klaus

Previously we were doing virt_lock() / virt_unlock() which automatically
were making sure to unlock GIL before locking virtmem, and to restore
GIL state to previous after virtmem lock happened. virt_unlock() was
unlocking just the virtmem lock without touching GIL at all - that works
because the running code would eventually release GIL as python
regularly does so to allowing multiple threads to run.

In the next patch however, we'll need to wait for in-progress-loading
page to complete, and that wait has to be done with GIL released (so
other python threads could run), and for doing so we'll need
functionality to make sure GIL is unlocked and retake it back, not tied
to virt_lock().

So factor it out.

NotifyChannel was introduced in c7c01ce4 (bigfile/zodb: ZODB.Connection
can migrate between threads on close/open and we have to care) to test
thread interaction specific to ZODB.

We'll however need NotifyChannel to do more threading test of virtmem
core, and this way the proper place for NotifyChannel is test_thread.py
itself.

Move it.

Both comments are from the beginning - from 9a293c2d (bigfile/virtmem:
Userspace Virtual Memory Manager) - but d53271b9 patch (bigfile/virtmem:
Big Virtmem lock) missed to update them.

No one was freeing RAMH structure itself, and thus ASAN reports e.g.:

==15935==ERROR: LeakSanitizer: detected memory leaks

Direct leak of 32 byte(s) in 1 object(s) allocated from:
    #0 0x7f29c89f1001 in __interceptor_calloc (/usr/lib/x86_64-linux-gnu/libasan.so.2+0x94001)
    #1 0x401da1 in zalloc include/wendelin/utils.h:65
    #2 0x408128 in shmfs_ramh_open bigfile/tests/../ram_shmfs.c:202
    #3 0x407611 in ramh_open bigfile/tests/../ram.c:81
    #4 0x402560 in fileh_open bigfile/tests/../virtmem.c:131
    #5 0x427ca1 in test_pagefault_savestate bigfile/tests/test_virtmem.c:1022
    #6 0x4281ba in main bigfile/tests/test_virtmem.c:1061
    #7 0x7f29c83b8b44 in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x21b44)

NOTE similar leak remains open in ram_close(), but it is a bit involved
to fix and the effort will be removed anyway after we switch to kernel
virtual memory manager. Besides ramh are opened and closed all the time
and ram only once.

Currently wendelin.core does not work on e.g. Debian 7, because that
distro has too old kernel without support for fallocate on tmpfs.
But the diagnostics of failure is not clear and looks like just being
out of memory:

    bigfile/tests/../virtmem.c:845 OOM      BUG!

what happens in fact is that

    - virtmem tries to allocate a page -> calls shmfs_alloc_page(),
    - fallocate() fails with "operation not supported" error code
    - virtmem sees this as page allocation failure,
    - tries to reclaim pages,
    - but there are no allocated pages at all -> OOM

Detect whether fallocate() error is operational error, or simply
"fallocate not supported" and if latter, report to user. Now it looks
like:

    bigfile/tests/../ram_shmfs.c:129 shmfs_alloc_page WARN: fallocate() not supported
    bigfile/tests/../virtmem.c:845 OOM      BUG!

/cc @Tyagov

Until now BigArrays could use only C-style ordering - where major index
is the first one.

Fortran ordering is the opposite - where major index is the last one -
and is used in Fortran world and sometimes by scientists in other areas.

As people keep on asking for Fortran-ordered BigArrays, let's add
support for it. The essential code change is to change 0'th index to
major index in __getitem__ and rest of the code.

For the reference: ndarray memory layout for different orders is
described here:

    http://docs.scipy.org/doc/numpy/reference/arrays.ndarray.html#internal-memory-layout-of-an-ndarray

Since 13c0c17c (bigfile/zodb: Format #1 which is optimized for small
changes) each ZBlk is split into chunks, and the procedure to load/save
blk data collects/disassembles the chunks.

Previously in bigfile/zodb tests, we were testing by verifying only [0]
element in each block, so this way most code for chunks
collection/disassembling was not tested.

Fix this aspect by making sure whole block content is as would-be
expected in tests.

It was reStructuredText already, but links showing was ugly, especially
when there were several links in the same line.

Use kernelnewbies style to refer to commits, when particular commit url
is not shown to user, only hyperlinked. This way it looks nicer.

With the target being to show it on pypi project page.

Now we have at least some readme, so this way it is more convenient.

This is a general readme about what wendelin.core is and how to use
ZBigArray from user point of view.

It was already there but very brief. Here we add text which tries to
explain to reader what is generally going on in the program.

ZBlk* objects are intermediate ZODB object in between data stored in
ZODB and memory pages managed by virtmem. As such, after they do their
job to either load data from DB to memory, or store from memory to DB,
it is not needed to keep them alive with duplicate content thus only
wasting memory.

ZBlk0 cares about this detail via "deactivating" ._v_blkdata in
loadblkdata() and __getstate__() prologues.

ZBlk1 did the same for load path in loadblkdata() prologue, but for
.__getstate__() it was not directly possible, because for ZBlk1 the
state is IOBTree, not one non-persistent object, and thus it first needs
to be processed by ZODB together with its subobjects on its way to
storage and only then all they deactivated.

So 13c0c17c (bigfile/zodb: Format #1 which is optimized for small
changes) only put TODO for memory-page -> DB path about not wasting
memory this way.

But the problem is relatively easy to solve:

    - we can deactivate ZData objects (leaf objects in ZBlk1.chunktab
      btree) by hooking into ZData.__getstate__() prologue;

    - we also need to care to deactivate chunks right away, which
      setblkdata() loaded to compare .data and found them to be not
      changed

This way we do not waste memory keeping intermediate ZData objects alive
with the same content as memory page after commit.

/cc @Tyagov

ZBlk1.setblkdata() has logic to detect CHUNKSIZE change, and if so
recreate whole chunktab from scratch for simplicity. There was a thinko
however - len(chunk.data) == CHUNKSIZE is ok and actually very often
happens when data does not have zeroes.

Because of this off-by-1 comparison mistake, ZData objects were
constantly created and thrown out instead of being reused which led to
fast ZODB growth.

Fix it.

/reported-by @Tyagov

Our current workloads are mostly a lot of small data changes and this is what
ZBlk1 was created for. Yes it has larger overhead for accessing data, but we
already painted the way how to handle this in 13c0c17c (bigfile/zodb: Format #1
which is optimized for small changes) -> move data deduplication/management to
server side.

So be it ZBlk1 the default for now.

/cc @Tyagov, @klaus

We check all pairs of possible formats and for every pair write some
data at file 0 block, check that it is in source format; then change
default format, write another data, check that file.blktab[0] changed
its type.

I.e. with this test we verify that the we can read data in old format
and change it incrementally to new. Or the other way, if data is in new
format, and we decide to migrate to old one, it also works.

/cc @Tyagov, @klaus

Our current approach is that each file block is represented by 1 zodb
object, with block size being 2M. Even with trailing \0 trimming, which
halves the overhead on average, DB size grows very fast if we do a lot
of small appends or changes. So another format needs to be introduced
which has lower overhead for storing small changes:

In general, to represent BigFile as ZODB objects, each file block could
be represented separately either as

    1) one ZODB object, or          (ZBlk0 - this what we have already)
    2) group of ZODB objects        (ZBlk1 - this is what we introduce)

with top-level BTree directory #blk -> objects representing block.

For "1" we have

    - low-overhead access time (only 1 object loaded from DB), but
    - high-overhead in terms of ZODB size (with FileStorage / ZEO, every change
      to a block causes it to be written into DB in full again)

For "2" we have

    - low-overhead in terms of ZODB size (only part of a block is overwritten
      in DB on single change), but
    - high-overhead in terms of access time
      (several objects need to be loaded for 1 block)

In general it is not possible to have low-overhead for both i) access-time, and
ii) DB size, with approach where we do block objects representation /
management on *client* side.

On the other hand, if object management is moved to DB *server* side, it is
possible to deduplicate them there and this way have low-overhead for both
access-time and DB size with just client storing 1 object per file block. This
will be our future approach after we teach NEO about object deduplication.

~~~~

As shown above in the last paragraph it is not possible to perform
optimally on client side. Thus ZBlk1 should be only an intermediate
solution until we move data management to DB server side, with main
criteria for ZBlk1 to keep it simple.

In this patch a simple scheme is used, where every block is divided into
chunks organized via BTree. When a block part changes, only corresponding
chunk is updated. Chunk size is chosen to be 4K which creates ~ 512
fanout for 2M block.

DB size after tests is changed as follows:

        bigfile     bigarray

ZBlk0     24K       6200K
ZBlk1     36K         36K

( slight size increase for bigfile tests is because of btree structures
  overhead )

Time to run tests stays approximately the same.

/cc @Tyagov, @klaus

- current ZBlk becomes format 0
- write format can be selected via WENDELIN_CORE_ZBLK_FMT env var
- upon writing a block we always make sure we write it in current write
  format - so if a block was previously written in one format, it could
  be changed on the next write.
- tox is prepared to test all write formats (so far only ZBlk0 there).

The reason is - in the next patch we'll introduce another format for
blocks which is optimized for small changes.

If we aim to have several kinds of ZBlk, the functionality to invalidate
a block and bind it to zfile is common and thus should be shared.

If we introduce a base class, it also makes sense to document what
.loadblkdata() and .setblkdata() should do there - in one place.

- we have logic to init ._v_zfile and ._v_blk there

- the same for ._v_blkdata - logic to init it is there + it is better to
  set variables right from instance creation, not hoping "it will be set
  outside from master"

  NOTE ._v_blkdata = None means the block was not yet loaded and
  generally fits into logic how ZBlk operates and thus the change is ok.

A lot of times data in blocks come shorter than block size and the rest
of the memory page is zeros (because it was pre-filled zeros by OS when
page was allocated).

Do a simple heuristic and trim those trailing zeros and not store them
into DB.

With this change size of DB created by running bigfile and bigarray
tests changes as following:

            bigfile     bigarray

    old     145M         35M
    new      24K          6M

Trimming trailing zeros is currently done with str.rstrip('\0') which
creates a copy. When/if needed this could be optimized to work in-place.

- to keep things uniform with counterpart .loadblkdata()
- so that master do not mess with ZBlk internals and works only through
  interface - this way it will be possible to use several
  kinds of ZBlk.

All those functions move data between DB and ._v_blkdata and only master
then connects data to memory page. Make that fact explicit.

Again, leftover from 4174b84a (bigfile: BigFile backend to store data in
ZODB).

The comment was a leftover there from 4174b84a (bigfile: BigFile backend
to store data in ZODB).

i.e. it is ok to copy smaller data into larger buffer.

- not only multiple of 8. We can do it by using uint8 typed arrays, and
it does not hurt performance:

In [1]: from wendelin.lib.mem import bzero, memset, memcpy
In [2]: A = bytearray(2*1024*1024)
In [3]: B = bytearray(2*1024*1024)

        memcpy(B, A)    bzero(A)        memset(A, 0xff)

old:    718 µs          227 µs / 1116   228 µs / 1055 (*)
new:    718 µs          176 µs / 1080   175 µs / 1048

    (*) the second number comes from e.g.

        In [8]: timeit bzero(A)
        The slowest run took 4.63 times longer than the fastest.
        This could mean that an intermediate result is being cached
        10000 loops, best of 3: 228 µs per loop

        so the second number is more realistic and says performance
        stays aproximately the same and only slightly improves.

When we serve indexing request, we first compute page range in backing
file, which contains the result based on major index range, then mmap
that file range and pick up result from there.

Page range math was however not correct: e.g. for positive strides, last
element's byte is (byte0_stop-1), NOT (byte0_stop - byte0_stride) which
for cases where byte0_stop is just a bit after page boundary, can make a
difference - page_max will be 1 page less what it should be and then
whole ndarray view creation breaks:

    ...
    Module wendelin.bigarray, line 381, in __getitem__
      view0 = ndarray(view0_shape, self._dtype, vma0, view0_offset, view0_stridev)
  ValueError: strides is incompatible with shape of requested array and size of buffer

( because vma0 was created less in size than what is needed to create view0_shape
  shaped array starting from view0_offset in vma0. )

Similar story for negative strides math - it was not correct neither.

Fix it.

/reported-by @Camata

We'll need this class in tests in the next patch.

It was already done from the beginning in 4174b84a (bigfile: BigFile
backend to store data in ZODB).

bigfile/zodb/tests: Make sure _p_invalidate() in Zblk.loadblk() does not lead to reloading data updated

Thanks to ZODB being MVCC this does not happen, but we better test
explicitly.

We'll need it in other places in the next patch.

e.g. on .shape