taskGNU Astronomy Utilities - Tasks: task #14572, Protect gal_data_t's array and...

 
 

You are not allowed to post comments on this tracker with your current authentication level.

task #14572: Protect gal_data_t's array and block pointers

Submitted by:  Mohammad Akhlaghi <makhlaghi>
Submitted on:  Sun 25 Jun 2017 06:13:50 PM UTC  
 
Should Start On: Sat 24 Jun 2017 10:00:00 PM UTCShould be Finished on: Sat 24 Jun 2017 10:00:00 PM UTC
Category: LibrariesPriority: 5 - Normal
Item Group: EnhancementStatus: Postponed
Privacy: PublicPercent Complete: 0%
Assigned to: NoneOpen/Closed: Open
Effort: 0.00

Fri 14 Jul 2017 04:21:31 PM UTC, comment #5:

After reading the Gnuastro manual for a while, if I have undertood it correctly, Gnuastro has two uses for gal_data_t objects; datasets and tiles. The reason to use the same data type for both is to be able to implement arbitrary tiling (two-layer tessellation, for example) without special cases (without the first-level tiles pointing to a dataset, and N-level tiles pointing to tiles of level N - 1).

My first idea to avoid dangling pointers under these circumstances is to implement a reference counter in gal_data_t. Every time a new tile is created (by one of the handling functions), the reference counter of its underlying gal_data_t is increased. And every time a tile is freed, its own reference counter is verified to be 0 and then the reference counter of its underlying gal_data_t is decreased.

Also when a tile is reassigned to another dataset of the same size (as is now done by changing manually tile->array and tile->block), the reference counter of its old dataset is decreased, while the reference counter of its new dataset is increased.

Antonio Diaz Diaz <antonio>
Project Member
Wed 28 Jun 2017 04:05:33 PM UTC, comment #4:

Thank you for the extra explanation Antonio. Unfortunately I am still a little confused. I completely agree with defining `gal_data_t' as an opaque structure and only access it through functions. I just don't understand the significance of the "subtile" (or "subarray") concept. Is it a new concept, or just a re-naming of the existing ones? Let me explain:

Currently, the larger entity is called a "Block" (because it is contiguous in memory) and the "sub"-entity is called a "tile", as the ASCII diagram in the book shows.

For example, let's assume we have the following two `gal_data_t's: `block' and `tile'. The first is a contiguous patch of memory and `block->block=NULL'. This shows that `block->array' is the start of this contiguous patch of memory. However, `tile->block=block' and `tile->array' points to somewhere within `block's allocated space.

The main advantage (purpose) of this system is that no extra allocation is necessary: two tiles may overlap, they may be read/written on separately (e.g., in parallel), and so on. Many Gnuastro programs currently rely on this feature to work in parallel. It is really up to the library programmer to be sure that they aren't writing to a tile before reading it in another tile that (might) overlap with the first one.

In this context, from what I understood, the "subtile" you mention are very similar to the already defined "block" (separately allocated patches of memory), am I correct?

Mohammad Akhlaghi <makhlaghi>
Project Administrator
Wed 28 Jun 2017 02:57:55 PM UTC, comment #3:

A 'subtile' is just a 'struct gal_data_t' initialized by 'gal_data_initialize' with a non-NULL pointer as 'array' (the larger parent array). My suggestion is to just wrap the gal_data_t's block concept (working with only a subset of the data) in a set of handling functions that guarantee that the 'array' and 'block' pointers are managed as documented in lib/gnuastro/data.h.

I proposed an array of subtiles just to make it possible to define as many tiles as are needed in a larger parent array. (It may be a linked list instead of an array). The subtile array starts empty, and subtiles are inserted or removed as needed.

'copy_subtile' is meant to ease the mapping of one particular region over a different larger parent array. (First duplicates subtile, then changes array and block pointers of the new subtile to point to the new larger parent array, then inserts the new subtile in the new larger parent array).

Maybe you would prefer to use other name for the 'subtiles' (sub-arrays?).

Antonio Diaz Diaz <antonio>
Project Member
Tue 27 Jun 2017 10:35:55 PM UTC, comment #2:

Thank you very much Antonio for this interesting suggestion.

I just don't clearly understand what you mean by "subtiles", do you mean separately allocated (smaller) arrays created from the larger parent array? This is what I interpret from the `get_num_subtiles' example.

If so, won't this drastically reduce the speed of processing over a randomly shaped and positioned tile over the dataset? Since we have to check many more boundaries. When we know the larger block is one contiguous patch of memory, we can just check for the tile boundaries and those of the larger block.

If I understood correctly, then if the block is not contiguous, managing the non-contiguity would be really hard (for the developer and the CPU).

Making `gal_data_t' opaque is indeed a great suggestion and I am all for doing so. We just have to come up with a good API. There are many applications of gal_data_t already in Gnuastro, so they can be a good example.

There is no rush tough, as you mentioned, designing a good API is not easy.

Mohammad Akhlaghi <makhlaghi>
Project Administrator
Tue 27 Jun 2017 08:59:08 PM UTC, comment #1:

Maybe you could implement the feature the other way. Instead of a 'block' pointer pointing to the larger array, you may implement an array of subtiles in (the opaque) 'gal_data_t'. This also allows arbitrary levels of tessellation, or mapping one particular region over several tiles, but makes it easier to keep tile->array and tile->block in sync and avoid use-after-free errors. The interface to the subtile array could be something like this:

// return subtile array size
int get_num_subtiles(gal_data_t *tile);
// get pointer to subtile
gal_data_t * get_subtile(gal_data_t *tile, int n);
// assemble and insert a new subtile in the array
bool insert_subtile(gal_data_t *tile, int n, ...);
// duplicate a subtile (perhaps from other tile) and insert it in the array
bool copy_subtile(gal_data_t tile, int n, gal_data_t subtile);
// delete subtile from array
bool delete_subtile(gal_data_t *tile, int n);

// this code maps the region defined by 'subtile2_3' of tile
// 'larger' over tile 'larger2'
gal_data_t * subtile2 = get_subtile(larger, 2);
gal_data_t * subtile2_3 = get_subtile(subtile2, 3);
copy_subtile(larger2, 0, subtile2_3);

Antonio Diaz Diaz <antonio>
Project Member
Sun 25 Jun 2017 06:13:50 PM UTC, original submission:

Gnuastro's generic data container (`gal_data_t') has two pointers that give information about the region of memory it is related to: `tile' and `block' (see the manual).

Currently there is no proper protection and not using these two pointer properly can cause some really annoying bugs for a programmer using these low-level features. So it would be very useful to not allow a library user to manually change these values and define certain functions to the manipulation of these properties.

In a discussion with Antonio Diaz Diaz, he suggested the following general suggestion, which I think would be very helpful for the library and its users.

"I think the standard way of "protecting" a data element in C is defining an opaque data type and accessing it only through handling functions. Glibc has a number of such opaque data types (for example the iconv interface). Lzlib also uses opaque data types (struct LZ_Encoder, struct LZ_Decoder).

But I see no way to prevent the user from freeing the allocated space and forgetting to call the handling function that sets tile->block to NULL. Designing a safe and easy to use API is not easy."

Mohammad Akhlaghi <makhlaghi>
Project Administrator

 

No files currently attached

 

Depends on the following items: None found

Items that depend on this one: None found

 

Carbon-Copy List
  • -unavailable- added by antonio (Posted a comment)
  • -unavailable- added by makhlaghi (Submitted the item)
  •  

    Do you think this task is very important?
    If so, you can click here to add your encouragement to it.
    This task has 0 encouragements so far.

    Only logged-in users can vote.

     

    Please enter the title of George Orwell's famous dystopian book (it's a date):

     

     

    No Changes Have Been Made to This Item

    Back to the top


    Powered by Savane 3.1-cleanup1