WL#4060: Online Backup: kernel updates for beta release

Implement these missing features of the backup kernel. Numbers in braces are 
estimates of developement time.

     - Use the backup stream library (WL#4063)                  [3d]
        Benefit: Backup stream library defines the format in
                 which backup image is written.

     - Thread shutdown handling 			        [2d]     
       Banefit: Otherwise can crash or leak memory when 
       backup thread is killed.                                               
                                                                                
     - Disable foreign key constraints when restoring tables.	[1d]
        Benefit: Restore will work even if there are foreign key
        constraints.                                        

        Note: This has been moved to WL#4150 : Online Backup : 
              Disable Foreign Key Constraint on Restore

Charset support
---------------

After small research on the subject, we use the following assumptions (please
email dev-backup if you find them wrong or incomplete):

1. All identifiers (table/db names etc) processed by parser are stored iusing
system_charset_info encoding (e.g. in the LEX_STRING structures obtained from
parser).

2. When server needs to identify a table when talking to a storage engine (e.g.
in open() call) it uses a path string where table and database names are encoded
using special charset. This path string for a given table/database name can be 
created using build_table_filename() function (defined in sql_table.cc). The
function assumes that the input table and database names are encoded using
system_charset_info.

Based on that:

- In backup kernel, all identifiers will be stored encoded with system_charset_info.

- The same encoding will be used when saving strings in a backup image (note
that name of the system charset is stored in the image's header).

- When reading backup image on a server with different system charset than the
one used during backup, strings will be translated to the restore server's
system charset.

- For any table passed to backup/restore driver, the driver will have access to
the internal representation of table's name as a path, the same as used in
storage engines.


Limitations
-----------

1. Beta kernel handles only databases and tables.

2. Beta kernel will not store in backup image's catalogue names of all charsets
needed to restore the image. 

If a server on which we restore will have all required charsets then the restore
operation will work normally, but if some charset is missing, then RESTORE will
quit with error. In future we can store info about all required charsets in the
catalogue and detect missing charsets before starting restore operation.

3. Beta kernel will not store any user and privilege info in the backup image.

Table name mangling
-------------------

Per HLS: backup/restore driver should have access to the internal representation
of table name. For that purpose new methods will be added to Table_ref class:

size_t Table_ref::internal_name(Iname_buf buf);
size_t Table_ref::internal_name(char *buf, size_t buflen);

Type Table_ref::Iname_buf will be a char array of size appropriate for storing
internal table name representation (FN_REFLEN?). So it can be used as follows:

Table_ref t;
Table_ref::Iname_buf tname;
size_t len= t.internal_name(tname);
DBUG_ASSERT(tname[len] == '\0');

Alternatively, user can decide itself what buffer size to use:

Table_ref t;
char tname[1024];
size_t len= t.internal_name(tname,1024);

Note: table name mangling will be implemented as a fix for BUG#33023.

Implementation of the catalogue services API
--------------------------------------------

The catalogue services API required by the backup stream library will be 
implemented using Image_info class. 

An instance of this class will store descriptions of backup image items in 
dynamically allocated entries which are instances of classes designed to store 
each type of item:

Image_info::Table_item	- for tables
Image_info::Db_item	- for databases

All these classes will inherit from Image_info::Item class and implement its 
virtual methods for:

- accessing meta-data of an item (CREATE statement and/or other data)
- creating a corresponding object using the meta-data read from archive.

These methods will be used to implement these catalogue services:

bcat_get_item_create_query()
bcat_get_item_create_data()
bcat_create_item()

The Item_info class will also have methods for adding items of various types to 
the catalogue. These will be used to implement.

bcat_add_item()

catalogue service which is used during restore operation to store inofo about 
items stored in the backup image.

Backup stream library browses contents of a catalogue using iterators. These 
will be implemented as specializations of Image_info::Iterator class which 
provides basic iterator operations (creating, proceeding to next item and 
accessing the current item). The following iterators will be implemented:

Image_info::Db_iterator	   - iterates over all databases
Image_info::Ditem_iterator - iterates over all tables of a given database

These classes will be used to implement

bcat_iterator_get()
bcat_iterator_next()
bcat_iterator_free()

bcat_db_iterator_get()
bcat_db_iterator_next()
bcat_db_iterator_free()

Note: backup stream library uses the following types of global iterators:

BSTREAM_IT_DB      - implemented with Image_info::Db_iterator class.
BSTREAM_IT_GLOBAL  - as above - the only (dynamic) global items we support are 
                     databases.
BSTREAM_IT_PERDB   - implemented with Image_info::Ditem_iterator class. 
BSTREAM_IT_PERTABLE - implemented as null iterator which returns no entries (we 
                      don't support per-table items in this version).

A limitation of this version is that we don't handle charsets and users in the 
image catalogue (they will still be present and used in the CREATE statements 
used to restore items). However, as a minimum we must store in the catalogue the 
common charset used to encode all remaining strings (we will use UTF-8) and the 
default charset of the server on which backup was created. We will store no user 
names in the catalogue and ignore (with warning) any user names read during 
restore.

BSTREAM_IT_CHARSET - implemented as two element iterator returning "UTF-8" 
                     charset followed by the server's default charset.
BSTREAM_IT_USER    - implemented as a null iterator returning no data.


Implementation of the Image_info class
--------------------------------------

Image_info class will implement backup catalogue and also stored the information 
of the backup image header. For the later it will inherit from 
bstream_header_info structure and store header info there. Additionally, for 
each snapshot included in the image, a pointer to instance of Snapshot_info 
object will be stored in Image_info::m_snap[] array. This instance will be used 
to store info about tables belonging to that image and define methods for 
processing the snapshot.

To access items stored in the catalogue Image_info will provide the following 
methods:

Db_item* get_db(uint pos) - return pointer to Db_item describing db stored at 
                            position pos in the catalogue, NULL if position is 
                            empty.

Table_item* get_table(unit k, unsigned long n) - return pointer to Table_item
                            describing n-th table stored in k-th snapshot, NULL 
                            if k or n are invalid.

To populate catalogue with items the following methods will be used:

Db_item* add_db(const Db_ref &db, uint pos) - create Db_item at position pos in 
                           the catalogue and store info about db there. Returns 
                           pointer to the newly created entry or NULL if 
                           operation failed.

Table_item* add_table(const Table_ref &t, uint k, unsigned long n) - create 
                           Table_item for table t stored in k-th snapshot at 
                           position n. Returns pointer to the newly created 
                           entry or NULL on error.

The Image_info class will manage memory for the Table_item and Db_item object 
instances. However, it will assume that the memory used by the Db_ref and 
Table_ref instances is managed externally and persists for the life span of the 
Image_info object. That is, the memory used for strings with table/db names is 
managed externally and these strings should exist as long as the catalogue 
exists. See below for description of how the memory is managed.

This is how various item types will be stored in the catalogue:

BSTREAM_IT_CHARSET - we store only 2 first charsets: the common string charset 
  and  the servers default charset. These will be stored in members 
  Image_info::common_cset and Image_info::default_cset as pointers to the 
  charset structure.

BSTREAM_IT_USER - in this version we don't store user info in the catalogue - 
  upon restore the names read from the image will be ignored.

BSTREAM_IT_PRIVILEGE - in this version we don't store privileges in the image.

BSTREAM_IT_DB - database items will be stored in a Image_info::m_db member which 
   is a dynamic array of Image_info::Db_item objects.

BSTREAM_IT_TABLE - n-th table of k-th snapshot will be stored at position n in 
   an dynamic array m_tables of the Snapshot_info object instance pointed by 
   m_snap[k]. 


Memory management
-----------------

During BACKUP/RESTORE process we need this memory:

- Memory for buffers for getting data from backup drivers.

 One buffer per driver is used, allocated inside Block_writer instance created  
 as a part of a Scheduler::Pump object used for that driver. Memory is 
 dallocated in pump's destructor. Size of the buffer is defined by 
 DATA_BUFFER_SIZE constant (1Mb currently).

- Memory for buffers for sending data to restore drivers.

  Single buffer is reused for all drivers (as data blocks are read sequentially 
  from a stream). The buffer is allocated inside backup stream library 
  (bstream_rd_data_chunk() function) using bstream_alloc() function. It is 
  deallocated when backup stream is closed.

- Memory to store Db_item instances for each database stored in the catalogue.

  These are stored in the m_dbs member of Image_info object. It is an instance 
  of Image_info::Databases class which uses DYNAMIC_ARRAY for storage (wrapped 
  by Dynamic_array class).

- Memory for the strings storing each database name (backup).

  In case when explicit list of databases is given as in BACKUP DATABASE 
  db1,db2,...,dbn TO ... the names of these databases are stored in the query 
  string and are returned from parser as LEX_STRING values. Kernel uses these 
  strings without copying them and allocating any new memory for them. 

  In case of BACKUP DATABASE * ... , the names are read from I_S.DB table and 
  copied to a String instance (which allocates memory to store the string). All 
  String instances used are appended to Backup_info::name_strings list. When 
  Backup_info object is deleted, the strings are freed.

  Note: this design is far from being elegant or optimal, but it works and 
  should be good enough for beta.

- Memory for the strings storing each database name (restore).

  Upon restore, database names are read from a backup stream. The memory for 
  storing them is allocated by backup stream library (in bstream_rd_string() 
  function) using bstream_alloc(). Note that memory is not freed by the library 
  and kernel needs to do that after the restore process is finished (see below).

- Memory to store Table_item instances for each table stored in the catalogue.

  For tables belonging to k-th snapshot, the Table_item instances are stored 
  inside Snapshot_info::m_tables member of class Tables. The latter uses 
  DYNAMIC_ARRAY for storage like Image_info::Databases.

- Memory for the strings containing each table's name (backup).

  The same as for databases - memory is allocated by String instances which are 
  appended to Backup_info::name_strings list and deleted in ~Backup_info.

- Memory for the strings containing each table's name (restore).

  The same as for databases, memory is allocated by backup stream library.

Memory (de)allocator for backup stream library
----------------------------------------------

Backup stream library (de)allocates memory using service functions:

void* bstream_alloc(unsigned long int howmuch)
void  bstream_free(void*)

However, not every memory allocated is freed by the library. Thus the
implementation must free any left-over memory.

The functions are implemented using class

Mem_allocator

with methods alloc() and free(). An instance of this class is created before any
backup/restore operation is started (in execute_backup_command()) and destroyed
when operation is completed.  This is done with functions:

prepare_stream_memory()
free_stream_memory()

This assumes only one BACKUP/RESTORE operation active at a time (otherwise we
couldn't use single Mem_allocator instance).

All memory blocks allocated with Mem_allocator are stored in a linked list, so
that in the destructor we can iterate over them and free them. When a block is
freed explicitly, it is removed from the list. 

Implementation
--------------

There are three patches commited which adapt backup kernel to use the stream
library. First patch reorganizes source tree a bit, changing names of some
source and header files. Second patch introduces necessary changes and fixes
problems in the backup stream library. Third patch modifies the backup kernel.

1. source tree chagnes: 
2. stream library patches: 
3. backup kernel modifications: 

Here is another patch which ensures that there is only single BACKUP/RESTORE
operation running at a time: