RPC Cache

SUNRPC 공통 cache의 목적과 기능

이 문서는 특히 NFS authentication에 사용하는 SUNRPC layer의 cache mechanism을 간략히 소개합니다. 새 caching framework는 오래된 exports table을 대체하고 다양한 종류의 값을 cache할 수 있게 합니다.

Cache들은 내용과 사용 목적은 크게 다를 수 있지만 구조는 비슷하며 공통 관리 code를 공유합니다. 대표 mapping은 IP address에서 client name, client name과 filesystem에서 export option, UID에서 GID list, local UID/GID와 remote UID/GID, network identity에서 cryptographic authentication용 public key입니다.

UID-to-GID cache는 NFS가 전달할 수 있는 GID가 16개로 제한되는 문제를 보완하고, local/remote ID mapping은 site마다 UID assignment가 일치하지 않는 환경을 지원합니다.

공통 code는 올바른 locking을 갖춘 lookup, positive와 `NEGATIVE` entry, expiry time과 사용 종료 뒤 제거, user space에 entry population 요청, user space의 직접 update를 처리합니다.

아직 완성되지 않은 cache entry에 의존하는 RPC request를 지연하고 entry가 완성되면 replay할 수도 있습니다. Expire된 오래된 entry를 정리하는 작업도 공통 계층이 담당합니다.

=========
RPC Cache
=========

This document gives a brief introduction to the caching
mechanisms in the sunrpc layer that is used, in particular,
for NFS authentication.

Caches
======

The caching replaces the old exports table and allows for
a wide variety of values to be caches.

There are a number of caches that are similar in structure though
quite possibly very different in content and use.  There is a corpus
of common code for managing these caches.

Examples of caches that are likely to be needed are:

  - mapping from IP address to client name
  - mapping from client name and filesystem to export options
  - mapping from UID to list of GIDs, to work around NFS's limitation
    of 16 gids.
  - mappings between local UID/GID and remote UID/GID for sites that
    do not have uniform uid assignment
  - mapping from network identify to public key for crypto authentication.

The common code handles such things as:

   - general cache lookup with correct locking
   - supporting 'NEGATIVE' as well as positive entries
   - allowing an EXPIRED time on cache items, and removing
     items after they expire, and are no longer in-use.
   - making requests to user-space to fill in cache entries
   - allowing user-space to directly set entries in the cache
   - delaying RPC requests that depend on as-yet incomplete
     cache entries, and replaying those requests when the cache entry
     is complete.
   - clean out old entries as they expire.

Cache datum, cache_detail과 operation 계약

Cache가 저장할 datum은 structure로 정의하며 보통 첫 member로 `struct cache_head`를 포함해야 합니다. Structure에는 key와 content도 들어갑니다. 각 cache element는 reference counted이고 cache 관리용 expiry time과 update time을 가집니다.

Cache를 설명하는 `struct cache_detail`은 hash table, 관리 parameter, 개별 item을 다루는 operation을 보관합니다.

`struct cache_head *alloc(void)`는 적절한 structure memory를 할당하고 그 안에 embedded된 cache object pointer를 반환합니다. 원문은 반환 pointer를 `cache_detail`이라고 쓰지만 operation signature와 뒤 문맥상 cache item의 embedded head를 뜻하는 설명으로 읽어야 하며, 번역에서는 signature를 그대로 보존합니다.

`void cache_put(struct kref *)`는 item의 마지막 reference가 떨어질 때 호출됩니다. 전달 pointer는 `cache_head.ref` field입니다. `cache_init`이 만든 reference와 `CACHE_VALID`일 때 `cache_update`가 만든 reference를 해제한 뒤 `alloc`이 할당한 memory를 해제해야 합니다.

`int match(struct cache_head *orig, struct cache_head *new)`는 두 structure의 key가 같으면 1, 다르면 0을 반환합니다. `void init(...)`은 `orig`의 key field를 `new`에 설정하며 shared object reference를 얻을 수 있습니다. `void update(...)`는 content field를 복사합니다.

Optional `cache_show(struct seq_file *m, struct cache_detail *cd, struct cache_head *h)`는 cache content를 나열하는 `/proc` file에서 item 하나를 보통 한 line으로 출력합니다.

`cache_request(...)`는 user space가 item을 instantiate하도록 요청 message를 buffer에 encode합니다. `*bpp`를 encoded message 뒤로 이동하고 `*blen`을 남은 free space만큼 줄이며 성공 시 0, 공간 부족이나 다른 문제면 음수를 반환합니다.

`cache_parse(...)`는 user-space response가 담긴 길이 `len`의 `buf`를 parse하고 `sunrpc_cache_lookup_rcu`로 item을 찾은 뒤 `sunrpc_cache_update`로 갱신해야 합니다. Cache는 `cache_register()`로 등록하며, 이후 오래된 data를 정기적으로 제거하는 cache 목록에 포함됩니다.

Creating a Cache
----------------

-  A cache needs a datum to store.  This is in the form of a
   structure definition that must contain a struct cache_head
   as an element, usually the first.
   It will also contain a key and some content.
   Each cache element is reference counted and contains
   expiry and update times for use in cache management.
-  A cache needs a "cache_detail" structure that
   describes the cache.  This stores the hash table, some
   parameters for cache management, and some operations detailing how
   to work with particular cache items.

   The operations are:

    struct cache_head \*alloc(void)
      This simply allocates appropriate memory and returns
      a pointer to the cache_detail embedded within the
      structure

    void cache_put(struct kref \*)
      This is called when the last reference to an item is
      dropped.  The pointer passed is to the 'ref' field
      in the cache_head.  cache_put should release any
      references create by 'cache_init' and, if CACHE_VALID
      is set, any references created by cache_update.
      It should then release the memory allocated by
      'alloc'.

    int match(struct cache_head \*orig, struct cache_head \*new)
      test if the keys in the two structures match.  Return
      1 if they do, 0 if they don't.

    void init(struct cache_head \*orig, struct cache_head \*new)
      Set the 'key' fields in 'new' from 'orig'.  This may
      include taking references to shared objects.

    void update(struct cache_head \*orig, struct cache_head \*new)
      Set the 'content' fields in 'new' from 'orig'.

    int cache_show(struct seq_file \*m, struct cache_detail \*cd, struct cache_head \*h)
      Optional.  Used to provide a /proc file that lists the
      contents of a cache.  This should show one item,
      usually on just one line.

    int cache_request(struct cache_detail \*cd, struct cache_head \*h, char \*\*bpp, int \*blen)
      Format a request to be send to user-space for an item
      to be instantiated.  \*bpp is a buffer of size \*blen.
      bpp should be moved forward over the encoded message,
      and  \*blen should be reduced to show how much free
      space remains.  Return 0 on success or <0 if not
      enough room or other problem.

    int cache_parse(struct cache_detail \*cd, char \*buf, int len)
      A message from user space has arrived to fill out a
      cache entry.  It is in 'buf' of length 'len'.
      cache_parse should parse this, find the item in the
      cache with sunrpc_cache_lookup_rcu, and update the item
      with sunrpc_cache_update.


-  A cache needs to be registered using cache_register().  This
   includes it on a list of caches that will be regularly
   cleaned to discard old data.

Lookup, cache_check와 deferred request

Cache에서 값을 찾으려면 key field를 채운 sample item의 `cache_head` pointer를 `sunrpc_cache_lookup_rcu`에 전달합니다. Lookup은 `->match`로 target entry를 식별하며, 찾지 못하면 valid data가 없는 새 entry를 만들어 cache에 추가합니다.

반환 item은 보통 `cache_check`에 넘깁니다. 이 함수는 data validity를 검사하고 필요하면 fresh data를 얻기 위한 upcall을 시작합니다. Negative entry이거나 upcall이 필요하지만 불가능하면 `-ENOENT`, upcall 진행 중이면 `-EAGAIN`, data가 valid하면 0을 반환합니다.

`cache_check`에는 보통 실제 RPC request에 embedded된 `struct cache_req *`를 전달할 수 있습니다. Entry가 최신이 아니지만 user space가 곧 정보를 제공할 가능성이 있으면 `struct cache_deferred_req` 형태의 request copy를 만듭니다.

Cache item이 valid해지면 deferred copy의 `->revisit`를 호출합니다. 이 method는 request가 다시 처리되도록 reschedule해야 합니다.

Lookup 결과를 `sunrpc_cache_update`에 넘겨 content를 설정할 수도 있습니다. 기존 item에 valid data가 있으면 그 item을 버리고 새 item을 만들어 inspection 중 content가 바뀌지 않게 합니다. Valid data가 없던 item이면 content를 복사하고 `CACHE_VALID`를 설정합니다.

Using a cache
-------------

To find a value in a cache, call sunrpc_cache_lookup_rcu passing a pointer
to the cache_head in a sample item with the 'key' fields filled in.
This will be passed to ->match to identify the target entry.  If no
entry is found, a new entry will be create, added to the cache, and
marked as not containing valid data.

The item returned is typically passed to cache_check which will check
if the data is valid, and may initiate an up-call to get fresh data.
cache_check will return -ENOENT in the entry is negative or if an up
call is needed but not possible, -EAGAIN if an upcall is pending,
or 0 if the data is valid;

cache_check can be passed a "struct cache_req\*".  This structure is
typically embedded in the actual request and can be used to create a
deferred copy of the request (struct cache_deferred_req).  This is
done when the found cache item is not uptodate, but the is reason to
believe that userspace might provide information soon.  When the cache
item does become valid, the deferred copy of the request will be
revisited (->revisit).  It is expected that this method will
reschedule the request for processing.

The value returned by sunrpc_cache_lookup_rcu can also be passed to
sunrpc_cache_update to set the content for the item.  A second item is
passed which should hold the content.  If the item found by _lookup
has valid data, then it is discarded and a new item is created.  This
saves any user of an item from worrying about content changing while
it is being inspected.  If the item found by _lookup does not contain
valid data, then the content is copied across and CACHE_VALID is set.

/proc/net/rpc channel protocol

각 cache에는 name이 있으며 등록하면 `/proc/net/rpc` 아래에 같은 이름의 directory가 생깁니다. 그 안의 `channel` file은 kernel과 user space가 cache를 채우기 위해 통신하는 경로이며 나중에 다른 cache interaction file이 추가될 수도 있습니다.

`channel` write는 datagram socket처럼 한 write 전체를 하나의 message로 cache parser에 전달합니다. Cache마다 해석은 다를 수 있지만 일반적으로 key, expiry time, content를 포함하며 해당 key의 item을 만들거나 갱신하고 expiry time을 설정하려는 요청입니다.

Read 방향에서는 lookup miss 또는 곧 expire할 수 있는 entry가 발견되면 user space에 update request를 등록하고 그 request가 `channel`에 나타납니다. 연속 read는 request를 차례로 반환하며 남은 request가 없으면 EOF를 반환합니다.

EOF 상태에서도 `select`나 `poll`로 readability를 기다리면 새 request가 추가될 때까지 block합니다. 일반 helper는 channel을 열고, readable 상태를 기다리고, request를 읽고, response를 쓴 뒤 반복합니다.

open the channel
  select for readable
  read a request
  write a response
loop

Helper가 죽었다가 재시작해도 응답하지 않은 request는 file에 남아 새 instance가 읽습니다. 각 cache의 `cache_parse`는 user space가 쓴 message를 처리해 error 또는 0을 반환하며, error는 write system call로 전달됩니다. `cache_request`는 cache item을 제공된 buffer에 request로 encode합니다.

Channel에 active reader가 없고 그 상태가 60초를 넘으면 새 request를 더 이상 추가하지 않습니다. 이후 valid entry를 찾지 못한 lookup은 모두 실패합니다. 이는 이전 NFS exports table이 authoritative하여 lookup miss를 확정적인 거부로 보던 동작과의 backward compatibility를 위한 면이 있습니다.

Populating a cache
------------------

Each cache has a name, and when the cache is registered, a directory
with that name is created in /proc/net/rpc

This directory contains a file called 'channel' which is a channel
for communicating between kernel and user for populating the cache.
This directory may later contain other files of interacting
with the cache.

The 'channel' works a bit like a datagram socket. Each 'write' is
passed as a whole to the cache for parsing and interpretation.
Each cache can treat the write requests differently, but it is
expected that a message written will contain:

  - a key
  - an expiry time
  - a content.

with the intention that an item in the cache with the give key
should be create or updated to have the given content, and the
expiry time should be set on that item.

Reading from a channel is a bit more interesting.  When a cache
lookup fails, or when it succeeds but finds an entry that may soon
expire, a request is lodged for that cache item to be updated by
user-space.  These requests appear in the channel file.

Successive reads will return successive requests.
If there are no more requests to return, read will return EOF, but a
select or poll for read will block waiting for another request to be
added.

Thus a user-space helper is likely to::

  open the channel.
    select for readable
    read a request
    write a response
  loop.

If it dies and needs to be restarted, any requests that have not been
answered will still appear in the file and will be read by the new
instance of the helper.

Each cache should define a "cache_parse" method which takes a message
written from user-space and processes it.  It should return an error
(which propagates back to the write syscall) or 0.

Each cache should also define a "cache_request" method which
takes a cache item and encodes a request into the buffer
provided.

.. note::
  If a cache has no active readers on the channel, and has had not
  active readers for more than 60 seconds, further requests will not be
  added to the channel but instead all lookups that do not find a valid
  entry will fail.  This is partly for backward compatibility: The
  previous nfs exports table was deemed to be authoritative and a
  failed lookup meant a definite 'no'.

Channel request/response record quoting

각 cache는 channel request와 response 형식을 자유롭게 정할 수 있지만 공통 helper가 지원하는 권장 형식이 있습니다. Record는 printable ASCII여야 하고 newline은 정확히 하나만 포함하며 반드시 끝에 위치해야 합니다.

Record의 field는 보통 space 하나로 구분합니다. Field 안에 space, newline, NUL character가 필요하면 quoting해야 합니다.

Field가 `\x`로 시작하면 뒤에 짝수 개의 hexadecimal digit이 와야 하며 각 digit pair가 field byte 하나를 나타냅니다.

그 밖의 형식에서는 backslash `\` 뒤에 octal digit 세 개를 써서 byte code를 나타냅니다. 다른 character는 그대로 취급하지만 최소한 space, newline, NUL, backslash 자체는 이 방식으로 quote해야 합니다.

request/response format
-----------------------

While each cache is free to use its own format for requests
and responses over channel, the following is recommended as
appropriate and support routines are available to help:
Each request or response record should be printable ASCII
with precisely one newline character which should be at the end.
Fields within the record should be separated by spaces, normally one.
If spaces, newlines, or nul characters are needed in a field they
much be quoted.  two mechanisms are available:

-  If a field begins '\x' then it must contain an even number of
   hex digits, and pairs of these digits provide the bytes in the
   field.
-  otherwise a \ in the field must be followed by 3 octal digits
   which give the code for a byte.  Other characters are treated
   as them selves.  At the very least, space, newline, nul, and
   '\' must be quoted in this way.