android upstreaming: Ashmem

Meta:
Roadmap id: CARD-106
Headline: Android Ashmem functionality has been upstreamed.
Acceptance:
   * implementation merged upstream into the kernel.
   * Android applications able to migrate to the upstream implementation
   * Validated (at least boot test) in linux-linaro Android (feel free to ask for testing resources)
   * OPTIONAL: Please consider formalizing the testing proposed bellow into acceptance criterion (again, feel free to ask for testing resources), releasing and including the test into our LAVA testing would be great

There is two threads of work in the below:
1) Work to get Android ashmem patch into staging
2) Work to provide an ashmem alternative which can be upstreamed, and working to convert the Android ashmem implementation to make use of.

Testing: Regular boot testing, testing with trivial custom C applications to test/stress new interface

[jakub-pavelek 2013-03-25] Not much progress for two months, not likely to hit 3.10 => moving to 3.11

Work items for 11.11:
Research ashmem-like madvise call for unlinked tmpfs files(Nov 21): DONE
Implement first pass fadvise FADV_VOLATILE based method for tmpfs(Nov 21): DONE
Submitted first pass to lkml (https://lkml.org/lkml/2011/11/21/651) (Nov 21): DONE
Get feedback (Got a mostly positive lwn writeup https://lwn.net/Articles/468896/) (Nov 23): DONE

Work items for 11.12:
Refactor ashmem patchs from AOSP in preparation for them to be included in staging(Dec 8): DONE
Sent refactored ashmem patches for staging to GregKH and Android team for review (Dec 8): DONE
Rework refactored ashmem patches per feedback (Dec 20): DONE
Submit refactored ashmem patches to staging. Merged! (Dec 21): DONE

Work items for 12.01:
Ashmem patches included in mainline staging! (Jan 9): DONE
Integrate simpler feedback into patch (Jan 12): DONE
Implement initial range-tree idea (suggested by akpm) in userspace (Jan 20): DONE
More range-tree testing (Jan 30): DONE

Work items for 12.02:
Utilize range-tree idea into kernel fadvise volatile implementation (Feb 9): DONE
Submit second pass fadvise patch to lkml & get feedback (Feb 9): DONE

Work items for 12.03:
Reimplemented my rangetree code using an rbtree(Mar 5): DONE
Address circular locking issue w/ current fadvise code (Mar 13): DONE
Send updated patch queue to lkml (Mar 16): DONE
Improved coalescing logic and algorithmic performance(Mar 20): DONE
Released a new iteration to lkml (Mar 20): DONE
Handle address_space structure bloat/overhead issue using hashtable(Mar 30): DONE

Work items for 12.04:
Sent out hashtable enabled iteration to lkml (Apr 6): DONE
Sort out issue of volatility persistence in closed tmpfs files (Apr 11): DONE
Resolve allocation/free circular locking issue from the fadvise patch (ashmem has same issue) (Apr 13): DONE
Submit v7 to lkml for review(April 13): DONE
First pass rework of upstreamed ashmem patch to use fadvise method(April 17): DONE
Submitted v7 to lkml for inclusion (April 24): DONE
Sent first pass rework of ashmem to use fadvise method to lkml for review (April 24): DONE

Work items for 12.05:
DaveC pushed back on v7 fadvise method, and wants me to rework it using the fallocate option so non-tmpfs filesystems can make use of it. Thus I need to research and prototype first pass fallocate implementation for tmpfs(May 25): DONE
Submit first pass fallocate volatile to lkml (May 25): DONE
Get feedback on first pass fallocate volatile & integrate suggested changes(May 31): DONE
Integrate improved pagecounting (May 31): DONE

Work items for 12.06:
Submit second pass fallocate volatile to lkml (June 1): DONE
Integrated community feedback and sent out a third iteration (June 1): DONE
Got another lwn writeup https://lwn.net/Articles/500382/ (June 6): DONE
Got some complex feedback on how the volatile reclaimation should happen. Trying to sort out how to best resovle how range purging should connect to the VM core (June 8): DONE
Developed an approach that tries to address how to reclaim volatile pages properly deeper in the VM core, sent out for RFC on lkml (June 12): DONE
Try to better grok the VM core: INPROGRESS
Do some performance analysis of the different appraoches I've tried: DONE
Improved page batching that gave 300% perf improvment to page based eviction. Unfortunately this is still 20x slower then the LRU based eviction (June 22): DONE
Per-feedback dropped interval tree appraoch and re-implemented using prio-trees(June 26): DONE
Submit to another iteration lkml for review (June 26): DONE

Work items for 12.07:
Implement preliminary implementation of volatile page lru deep in the VM (July 27): DONE
Sent iteration for feedback to lkml (July 27): DONE

Work items for 12.08:
Get initial actual ashmem usage stats (size, freq) (Aug 3): DONE
Per feedback, remove activation boosting on marking nonvolatile (Aug 7): DONE
Drop prio-tree for simple rbtree, per community feedback (Aug 10): DONE
Discuss volatile ranges at Kernel Summit/Linux Plumbers (Aug 27-31st): DONE

Work items for 12.09:
Discussed interface needs with Mozilla develoers (Sep 4): DONE
Implement byte-range accounting instead of page-range (Sep 6): DONE
Pinged Andi Kleen on his MADV_DISPOSABLE approach (Sep 17): DONE
Implement first-pass SIGBUS on purged page access (Sept 25): DONE
Validate SIGBUS on purged access is compatable with Andorid (Booted with Android and saw no problems - Sept 27): DONE
Meet with Taras from Mozilla to disucss details on SIGBUS req(Sep 27): DONE
Generate summary of interface needs and semantics (Sep 28): DONE
Send out updated patch set with longer description and discussion points (Sep 28): DONE

Work items for 12.11:
Review Minchan's VMA based approach for anonymous memory, and see how it can be aligned with the tmpfs file based approach I've been pushing(Nov 28): DONE
Fixed some bugs in Mincha's work, and hacked together a way to support tmpfs (as well as other files) and sent to lkml for comment (Nov 28): DONE
Fix VMA volatile purged state handling (Nov 30): DONE

Work items for 12.12:
Review Minchan's v3 vma based approach, found an critical issue and reported it(Dec 11): DONE

Work items for 13.01:
Review Minchan's v5 vma based approach (Jan 24): DONE

Work items for 13.03:
Review Minchan's v7 non-vma based approach(March 26): DONE

Work items for 13.04:
First pass to make Minchan's non-vma based approach work for files sent to lkml (April 4): DONE
Got madvise style interface working on mmaped file pages as well(April 16): DONE
Got sigbus on purged file access sorted out (April 16): DONE
Prep for lsf-mm discussion (April 17): DONE
Sent background info for for lsf-mm here http://permalink.gmane.org/gmane.linux.kernel.mm/98676 (April 17): DONE
Presented at lsf-mm. My summary is here http://permalink.gmane.org/gmane.linux.kernel.mm/98848 (April 22): DONE

Work items for 13.05:
Rework & recombine Minchan and my work into a more coherant patchset: DONE
Sent reworked patchset to Minchan for review(May 3): DONE
Fix lsf-mm issue of unmarking ranges that are mapped into a already volatile range (May 8): DONE
Integrated Minchan's suggested changes (May 14): DONE

Work items for 13.06:
Further discussion and rework of patches (June 10): DONE
First pass unifying purging logic for file&anon pages (June 11): DONE
Resend to lkml for feedback(June 11): DONE
Fix file purging logic so backing files get hole-punched: TODO
Re-integrate page purging for swapless systems: TODO
Start real push for upstream: TODO

Work items for backlog:
Re-Integrate hash mapping: TODO
Integrate ashmem driver to use the new volatile method: TODO
Try to drive to some form of conensus on how this should be done: TODO
Look into using shmem_mmap instead of ashmem's usage of shmem_set_file for staging: TODO
Merge volatile range functionality upstream: TODO
Make any necessary changes to Android ashmem driver or Android libraries: TODO
Merge required Android changes via AOSP: TODO