This allows writeout code not to scan whole pagemap to find dirty pages
to write out, which should be faster.

But more importantly iterating whole pagemap on writeout would become
unsafe, when in upcoming patch storeblk() will be called with virt_lock
released: because there pagemap could be modified e.g. due to processing
other read accesses.

So maintain fileh->dirty_pages list and use it when we need to go
through dirtied pages.

Updates: #6

Currently fileh_dirty_writeout() writes page via storeblk() in order -
- those with lower ->f_pgoffset are stored first.

This happens because current fileh_dirty_writeout() iterates whole
pagemap to find dirty pages and pagemap iteration is ordered by
f_pgoffset.

In upcoming patch we'll rework writeout code not to iterate through
whole pagemap, but only through dirty pages. However the property that
pages are emitted in canonical order is useful, so let's make sure via
tests this will stay preserved:

In mkdirty2() we modify pages in 2, 0 order, but the latter code checks
(via storeblk_trace()) they were actually stored in 0, 2 order.

Just update to latest CCAN for it to be a fresh one.

13c0c17c (bigfile/zodb: Format #1 which is optimized for small changes)
used BTree to organize ZBlk1 block's chunks and for loadblkdata() added
"TODO we are missing to free internal BTree structures on data load".

#3 besides other
things showed that even when we deactivate ZData objects, we are still
keeping them as ghosts occupying memory and the same for IOBucket
objects.

This all happens because there is no proper way to deactivate whole
btree - including internal buckets objects. And since internal buckets
are not deactivated, they stay in picklecache and thus hold a reference
to ZData objects and ZData objects in turn, even if explicitly
deactivated, stay in memory.

We can fix this all via implementing whole-btree deactivation procedure.

To do so we need to iterate over all btree buckets recursively, but
unfortunately there is no BTree API to access/iterate btree's buckets.
We can however still get reference to first top-level buckets via
gc.get_referents(btree) and then scan buckets further without hacks.

gc.get_referents(btree) is a hack, but

- it works in O(1)  (we only get pointers from btree, not scanning all
  gcable objects and deducing them)
- it works reliable if we filter out non-interesting objects.

So in the end it works.

Before the patch loading more and more ZBlk1 data with objgraph
instrumentation was showing itself like

    #                                    Nobj        δ
    wendelin.bigfile.file_zodb.ZData     7168      +512
    BTrees.IOBTree.IOBucket               238       +17
    BTrees.IOBTree.IOBTree                 14        +1

and after this patch we now have

    BTrees.IOBTree.IOBTree                 14        +1

we cannot remove that "IOBTree + 1", since ZBlk1 is holding direct
reference on it (via .chunktab) and we have to keep ZBlk1 live with
._v_zfile and ._v_zblk set for invalidation to work. "+1 IOBtree" is
however small - 144 bytes per 2M (= 0.006%) so we can neglect that the
same way we neglect keeping ZBlk1 staying live for each block.

The following started to appear after recent gcc upgrade on my host:

bigfile/virtmem.c: In function `vma_on_pagefault':
bigfile/virtmem.c:696:9: warning: implicit declaration of function `usleep' [-Wimplicit-function-declaration]
         usleep(10000);  // XXX with 1000 uslepp still busywaits

This updates and fixes 487e5226 (setup: specify setuptools location
explicitly when calling make.) to use @kazuhiko original idea to
propagate only setuptools location. The reason is - when propagating
whole sys.path things break under tox tests:

---- 8< ----
========================================================================== test session starts ===========================================================================
platform linux2 -- Python 2.7.12, pytest-2.9.2, py-1.4.31, pluggy-0.3.1
rootdir: /home/kirr/src/wendelin/release/wendelin.core, inifile:
collected 33 items

bigarray/tests/test_arrayzodb.py .......
bigarray/tests/test_basic.py ........
bigfile/tests/test_basic.py ....
bigfile/tests/test_filefile.py .
bigfile/tests/test_filezodb.py ........
bigfile/tests/test_thread.py ....
lib/tests/test_calc.py .

======================================================================= 33 passed in 14.14 seconds =======================================================================
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/tfault.c lib/bug.c lib/utils.c 3rdparty/ccan/ccan/tap/tap.c  -o bigfile/tests/tfault.t
t/tfault-run bigfile/tests/tfault.t faultr on_pagefault
ok 1 - !pagefault_init()
Fatal Python error: Py_Initialize: Unable to get the locale encoding
  File ".../wendelin.core/.tox/py27-ZODB3-zblk0-fs-numpy110/lib/python2.7/encodings/__init__.py", line 123
    raise CodecRegistryError,\
                            ^
SyntaxError: invalid syntax

Current thread 0x00007f9b80024780 (most recent call first):
t/tfault-run: line 28: 21521 Аварийный останов         (core dumped) gdb -q -batch $tfault core > core.info
E: can't gdb(core)
Makefile:189: ошибка выполнения рецепта для цели «faultr.tfault»
make: *** [faultr.tfault] Ошибка 1
rm bigfile/tests/test_virtmem.t bigfile/tests/test_ram.t bigfile/tests/tfault.t bigfile/tests/test_pagemap.t
error: Failed to execute `make test`
ERROR: InvocationError: '.../wendelin.core/.tox/py27-ZODB3-zblk0-fs-numpy110/bin/python setup.py test'
________________________________________________________________________________ summary _________________________________________________________________________________
ERROR:   py27-ZODB3-zblk0-fs-numpy110: commands failed
---- 8< ----

What happens here is:

- gdb is used in automated tests
- gdb is linked with libpython3.5
- tox is currently running tests with python27
- setup.py sets PYTHONPATH to whole path from python27
- gdb, upon starting, initializes python runtime, which tries to load
  py27 modules under py35 -> oops.

So propagating only setuptools location practically solves the issue for
now, but still there is potential risk that in future, there will be
other modules put in the same location as setuptools (location is parent
dir of a module/package) which python tries to load on startup and which
might be incompatible between 2 & 3.

Thus not setting PYTHONPATH at all - e.g. creating environments
virtualenv way - would be better, but buildout fundamentally works the
other way. We can not also use -c 'buildout sys.path hack' in $PYTHON
itself, as $PYTHON is used in general way inside Makefile.

So let the hack with setuptools location in PYTHONPATH stay there until
it practically works.

If wendelin.core is built under buildout and setuptools exists only in
buildout environment, 'python setup.py' called inside make will fail
without this change.

    Building 'wendelin.core'
    Running easy_install:
    "/path/to/python2.7" "-c" "import sys; sys.path[0:0] = ['/path/to/setuptools-19.6.2-py2.7.egg']; from setuptools.command.easy_install import main; main()"...
    path_list=['/path/to/setuptools-19.6.2-py2.7.egg']
    ...
    <<< setup.py: os.system('make %s PYTHON="%s"' % (target, sys.executable))
    ...
    make[1]: Leaving directory '/tmp/xxx/wendelin.core-0.6/3rdparty/ccan'
    /path/to/python2.7 setup.py ll_build_ext --inplace
    Traceback (most recent call last):
      File "setup.py", line 18, in <module>
        from setuptools import setup, Extension, Command, find_packages
    ImportError: No module named setuptools
    Makefile:40: recipe for target 'bigfile/_bigfile.so' failed
    make: *** [bigfile/_bigfile.so] Error 1
    error: Setup script exited with error: Failed to execute `make all`

[ @kirr: as a solution we are propagating whole python path via make.

  This should cover both setuptools case, and any other future potential
  "preloaded-by-buildout" egg. ]

/reviewed-on !1

@kazuhiko reports that wendelin.core build is currently broken on Python 3.5.
Indeed it was:

    In file included from bigfile/_bigfile.c:37:0:
    ./include/wendelin/compat_py2.h: In function ‘_PyThreadState_UncheckedGetx’:
    ./include/wendelin/compat_py2.h:66:28: warning: implicit declaration of function ‘_Py_atomic_load_relaxed’ [-Wimplicit-function-declaration]
         return (PyThreadState*)_Py_atomic_load_relaxed(&_PyThreadState_Current);
                                ^
    ./include/wendelin/compat_py2.h:66:53: error: ‘_PyThreadState_Current’ undeclared (first use in this function)
         return (PyThreadState*)_Py_atomic_load_relaxed(&_PyThreadState_Current);
                                                         ^
    ./include/wendelin/compat_py2.h:66:53: note: each undeclared identifier is reported only once for each function it appears in
    ./include/wendelin/compat_py2.h:67:1: warning: control reaches end of non-void function [-Wreturn-type]
     }
     ^

The story here is that in 3.5 they decided to remove direct access to
_PyThreadState_Current and atomic implementations - because that might
semantically conflict with other headers implementing atomics - and
provide only access by function.

Starting from Python 3.5.2rc1 the function to get current thread state
without asserting it is !NULL - _PyThreadState_UncheckedGet() - was added:

    https://github.com/python/cpython/commit/df858591

so for those python versions we can directly use it.

After the fix wendelin.core tox tests pass under all python2.7, python3.4 and python3.5.

More context here:

    https://bugs.python.org/issue26154
    https://bugs.python.org/issue25150

Fixes: #1

_PyThreadState_Current_GET() is a function to get current python thread
state without asserting it is !NULL. It was added as part of d53271b9
(bigfile/virtmem: Big Virtmem lock)

We are going to adapt it to Python 3.5 (see next patch), so before doing
so move it to our compatibility place.

In the new place the name is _PyThreadState_UncheckedGet -- like such
function is named in Python 3.5 (again, see next patch).

Updates: #1

Now that ZODB 5.0 eggs are starting to appear (see e.g. [1] for context)
let's limit ZODB4 test setup to actually install ZODB4, not 5.

[1] https://groups.google.com/forum/#!topic/zodb/P05S0pyUbAM

Upon @jp request.

The link is absolute URL, since the readme can be shown in a lot of
places (on lab.nexedi.com, on pypi, on github, etc...)

We might also change the link to demo_zbigarray.py to be absolute URL
because of pypi case in the future.

Since the beginning of pagemap (45af76e6 "bigfile/pagemap: specialized
{} uint64 -> void * mapping") we had a bug sitting in
__pagemap_for_each_leaftab() (non-leaf iterating logic behind
pagemap_for_each):

After entry to stack-down was found, we did not updated tailv[l]
accordingly. Thus if there are non-adjacent entries an entry could be
e.g. emitted many times:

     l 3  __down 0x7f79da1ee000
     tailv[4]: 0x7f79da1ee000
      -> tailv[4] 0x7f79da1ee000  __down 0x7f79da1ed000

     l 4  __down 0x7f79da1ed000
     tailv[5]: 0x7f79da1ed000
     h 5  l 5  leaftab: 0x7f79da1ed000      <--
      lvl 5  idx 169  page 0x55aa
    ok 9 - pagemap_for_each(0) == 21930

     l 5  __down (nil)
     tailv[4]: 0x7f79da1ee008
      -> tailv[4] 0x7f79da1ee008  __down 0x7f79da1ed000

     l 4  __down 0x7f79da1ed000
     tailv[5]: 0x7f79da1ed000
     h 5  l 5  leaftab: 0x7f79da1ed000      <--
      lvl 5  idx 169  page 0x55aa
    not ok 10 - pagemap_for_each(1) == 140724106500272

And many-time-emitted entries are not only incorrect, but can also lead
to not-handled segmentation faults in e.g. fileh_close():

    https://lab.nexedi.com/nexedi/wendelin.core/blob/v0.6-1-gb0b2c52/bigfile/virtmem.c#L179

    /* drop all pages (dirty or not) associated with this fileh */
    pagemap_for_each(page, &fileh->pagemap) {
        /* it's an error to close fileh to mapping of which an access is
         * currently being done in another thread */
        BUG_ON(page->state == PAGE_LOADING);
        page_drop_memory(page);
        list_del(&page->lru);                           <-- HERE
        bzero(page, sizeof(*page)); /* just in case */
        free(page);
    }

( because after first bzero of a page, the page is all 0 bytes including
  page->lru{.next,.prev} so on the second time when the same page is
  emitted by pagemap_for_each, list_del(&page->lru) will try to set
  page->lru.next = ... which will segfault. )

So fix it by properly updating tailv[l] while we scan/iterate current level.

NOTE

This applies only to non-leaf pagemap levels, as leaf level is scanned
with separate loop in pagemap_for_each. That's why we probably did not
noticed this earlier - up until now our usual workloads was to change
data in adjacent batches and that means adjacent pages.

Though today @Tyagov was playing with wendelin.core in some other way and
it uncovered the bug.

In the time when README.rst was initially introduced (58279ac7 "readme:
Initial draft") GitLab was not handling relative links well and it was
necessary to construct them properly by hand.

Nowdays GitLab automatically adds namespace and project and blob/ref/
prefix to relative URL link, so there is no need to specify them
manually.

Actually specifying the prefix manually makes URL invalid, as it becomes
something like

    https://lab.nexedi.com/nexedi/wendelin.core/blob/master/wendelin.core/blob/master/demo/demo_zbigarray.py

Fix it.

This continues c7750965 (changelog: Convert it to pretty rst) - without
.rst extension gitlab shows this file as plain text.

>= 1.6 was already using latest in 1.6 series, but >= 1.6.2 is more explicit.

Also: in 1.6.2 NEO switched from MySQL-python to mysqlclient:

    neoppod@5f0c93f5

so we switch it too.

Namely

    1.8.x, 1.9.x -> 1.10.x -> 1.11.x

Just update to latest CCAN for it to be a fresh one.

Throught the modules we use there are no real updates, just a fix for
one warning in array_size.

For ZBlk1 we already compare ZData content about whether it was changed
compared to data already stored to DB, and do not store it twice if data
is the same.

However ZBlk itself is always marked as changed, if corresponding memory
page was dirtied. This results in transactions like

Trans #33915309 tid=03b6944919befeee time=2016-04-17 22:01:06.034237 offset=140320105842
    status=' ' user='...' description='...'
  # ... other parts, but no ZData here
  data #2 oid=000000000026fc4c size=79 class=wendelin.bigfile.file_zodb.ZBlk1

where ZBlk1 is committed the same without necessity.

NOTE we cannot avoid committing ZBlk in all cases, because it is used to signal
    other DB clients that a ZBlk needs to be invalidated and this way associated
    fileh pages are invalidated too.

    This cannot work via ZData, because ZData don't have back-pointer to
    ZBlk1 or to corresponding zfile.

Starting from setuptools 19.4, more concrete from the following commit:

    https://github.com/pypa/setuptools/commit/ebc54982

setuptools sorts namespaced packages .__path__ to be in sync with sys.path .
That however breaks for wendelin.core used from in-tree or installed in
development mode, because we are doing tricks in top-level import redirector
(see e870781d "Top-level in-tree import redirector"):

    (z+numpy.v2)kirr@teco:~/tmp/trashme/wendelin.core$ python -c 'import wendelin'
    Traceback (most recent call last):
      File "<string>", line 1, in <module>
      File "wendelin.py", line 39, in <module>
        __import__('pkg_resources').declare_namespace(__name__)
      File "/home/kirr/src/wendelin/venv/z+numpy.v2/local/lib/python2.7/site-packages/pkg_resources/__init__.py", line 2081, in declare_namespace
        _handle_ns(packageName, path_item)
      File "/home/kirr/src/wendelin/venv/z+numpy.v2/local/lib/python2.7/site-packages/pkg_resources/__init__.py", line 2026, in _handle_ns
        _rebuild_mod_path(path, packageName, module)
      File "/home/kirr/src/wendelin/venv/z+numpy.v2/local/lib/python2.7/site-packages/pkg_resources/__init__.py", line 2050, in _rebuild_mod_path
        orig_path.sort(key=position_in_sys_path)
      File "/home/kirr/src/wendelin/venv/z+numpy.v2/local/lib/python2.7/site-packages/pkg_resources/__init__.py", line 2045, in position_in_sys_path
        return sys_path.index(_normalize_cached(os.sep.join(parts)))
    ValueError: '/home/kirr/tmp/trashme' is not in list

Here wendelin.py added /home/kirr/tmp/trashme/wendelin.core to .__path__ and
setuptools' _handle_ns() wants to order that dir's parent in correspondence
with sys.path, but parent path is not there - oops.

We can workaround the problem, by first not initializing .__path__ and letting

    __import__('pkg_resources').declare_namespace(__name__)

fully handle and initialize it, and only after it is done we make the
correction for wendelin modules located not under .../wendelin.core/wendelin/
but under .../wendelin.core/ .

Importing was tested to work with the fix with both setuptools 20.6.7 and older
setuptools 17.1.1, i.e. here we should not be breaking backward compatibility.

/reported-by @tatuya, @Camata, @Tyagov

/reviewed-on kirr/wendelin.core!1

Commit ab9ca2df (bigarray: Add support for FORTRAN ordering) added
ability to define array order, but there I made a mistake of not caring
about how previously-saved to DB arrays would be read back.

The thing is BigArray gained new data member ._order which is
automatically saved to DB thanks to ZBigArray inheriting from
Persistent; on load-from-db path we just read object state from DB,
which for ZBigArray is dict, and restore object attributes from it.

But for previously-saved data, obviously, there is no 'order' entry and thus
this way restored objects are restored not in full to current code expectations
and it can boom e.g. this way:

    zarray.resize((new_one,old_shape[1]))
  Module wendelin.bigarray, line 190, in resize
    self._init0(new_shape, self.dtype, order=self._order)
  AttributeError: 'ZBigArray' object has no attribute '_order'

Solution to fix is: on restore-from-DB path, see if a data member is not
present on restored object, and if it has default value in BigArray set it to
that.

( code to get function defaults is from
  http://stackoverflow.com/questions/12627118/get-a-function-arguments-default-value )

/cc @Tyagov, @klaus

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.