Support for bzip compressed modules

The patch implements this support by changing sepol_policy_file_t to support decompressing files or memory areas into a private memory copy. This support is optional - dlopen is used so that a hard dependency to libbz2 is not introduced. I took the approach of decompressing the entire file or memory area because:

* It is very simple
* The current code depends on the ability to seek within policy files - this is not really possible within compressed streams using the bzip2 library.

The downsides are:

* Increased memory usage
* No transparent support for compressed writing with an fd based policy file.

I didn't want to add additional set functions - I would have preferred to allow sepol_policy_file_set_[mem,fd] to transparently open compressed streams with functions to set other behaviors as options stored in sepol_policy_file_t structs. This was not possible becuase the current set functions do not return errors.

Comments appreciated. Some very crude benchmarking below (note that I am using a patched semodule to allow the globbing syntax - patch for that to follow). The summary is that there is substantial space savings at the expense of some increase in time to complete common actions. An acceptable trade-off in my opinion.

Anyone have suggestions for something as simple as time but for max memory usage?

Quoted 1 line · Karl MacMillan

The patch implements this support by changing sepol_policy_file_t to support decompressing files or memory areas into a private memory copy. This support is optional - dlopen is used so that a hard dependency to libbz2 is not introduced. I took the approach of decompressing the entire file or memory area because:

Why don't we want to depend on libbz, if we are building with bz2
support?

Quoted 8 lines

* It is very simple
* The current code depends on the ability to seek within policy files - this is not really possible within compressed streams using the bzip2 library.

The downsides are:

* Increased memory usage
* No transparent support for compressed writing with an fd based policy file.

Quoted 1 line

I didn't want to add additional set functions - I would have preferred to allow sepol_policy_file_set_[mem,fd] to transparently open compressed streams with functions to set other behaviors as options stored in sepol_policy_file_t structs. This was not possible becuase the current set functions do not return errors.

Do we really care about the memory usage, my instinct would be to drop
the FILE specific code and just dump everything into memory and then call the mem_set function and thus. have only one decompression loop (adding the fd version is simple then too).
Calling fstat(fileno(fp)) to read the policy in is probably easier than
a loop.

Quoted 3 lines

Comments appreciated. Some very crude benchmarking below (note that I am using a patched semodule to allow the globbing syntax - patch for that to follow). The summary is that there is substantial space savings at the expense of some increase in time to complete common actions. An acceptable trade-off in my opinion.

Anyone have suggestions for something as simple as time but for max memory usage?

There's memusage in glibc-utils.

---- code ----

The bz2 code looks fine, although the += BUFSIZE in one loop and *= 2
in the other is weird, and there's a couple of minor nits in the interface:

. check is always true in callers, and I'm not sure why you'd have it zero.

. All code paths have:

if (set_foo_bz2() == FAILED)
set_foo();

...which tells me set_foo_bz2() should do that ... in fact it seems sane to just change set_foo() to check of bz2ness and do the right thing, without having to alter the callers.

. A personal minor nit is that free(NULL) works fine, so don't work around it (this idiom seems to be used in sepol).

. sepol_policy_file_free_data() is also called multiple times at the end of the set_foo_bz2() functions (once inside set_foo() and then explicitly immediately after).

I assume the only reason you went with bzip2 over gzip is the "have to
init yourself in the set_mem case"?

help you get that bit done if you want ... this will drop CPU/memory/dependency requirements (although expecting all Linux to have libbz now isn't a big deal, IMO).

Quoted 11 lines · James Antill

Quoted 5 lines · Karl MacMillan

The patch implements this support by changing sepol_policy_file_t to support decompressing files or memory areas into a private memory copy. This support is optional - dlopen is used so that a hard dependency to libbz2 is not introduced. I took the approach of decompressing the entire file or memory area because:

Why don't we want to depend on libbz, if we are building with bz2
support?

This allows the same binary to be installed with or without libbz2. Since libsepol gets pulled into so many installs, it seems preferable to not add additional dependencies.

On the other hand, I don't have a strong preference about that part of the patch. If libbz2 is deemed sufficiently available (or even libz I guess) we can just directly link. Perhaps with compile time options.

Quoted 8 lines · James Antill

Quoted 5 lines · Karl MacMillan

I didn't want to add additional set functions - I would have preferred to allow sepol_policy_file_set_[mem,fd] to transparently open compressed streams with functions to set other behaviors as options stored in sepol_policy_file_t structs. This was not possible becuase the current set functions do not return errors.

Quoted 7 lines

Do we really care about the memory usage, my instinct would be to drop
the FILE specific code and just dump everything into memory and then call the mem_set function and thus. have only one decompression loop (adding the fd version is simple then too).
Calling fstat(fileno(fp)) to read the policy in is probably easier than
a loop.

Not certain what you are getting at - both code paths result in an uncompressed copy of the compressed data in memory. The only difference is whether we are decompressing from an fd or from another memory buffer.

Quoted 3 lines

. check is always true in callers, and I'm not sure why you'd have it zero.

The magic number checking seems fragile - I'm assuming it might be necessary to force the stream as compressed at some point. Since we are maintaining ABI for this library (and these functions), seems better to be safe.

Quoted 5 lines

. All code paths have:

if (set_foo_bz2() == FAILED)
set_foo();

Quoted 4 lines

...which tells me set_foo_bz2() should do that ... in fact it seems sane to just change set_foo() to check of bz2ness and do the right thing, without having to alter the callers.

Note my comments with the original patch - this isn't possible because set_foo() has a void return and we want to maintain binary compatibility.

Quoted 17 lines · Karl MacMillan

Quoted 15 lines · James Antill

Quoted 5 lines · Karl MacMillan

I didn't want to add additional set functions - I would have preferred to allow sepol_policy_file_set_[mem,fd] to transparently open compressed streams with functions to set other behaviors as options stored in sepol_policy_file_t structs. This was not possible becuase the current set functions do not return errors.

Do we really care about the memory usage, my instinct would be to drop
the FILE specific code and just dump everything into memory and then call the mem_set function and thus. have only one decompression loop (adding the fd version is simple then too).
Calling fstat(fileno(fp)) to read the policy in is probably easier than
a loop.

Quoted 3 lines

Not certain what you are getting at - both code paths result in an uncompressed copy of the compressed data in memory. The only difference is whether we are decompressing from an fd or from another memory buffer.

Just that it seems easier to have the set_fp() function load all the
data into memory and call the set_mem() function, and have all of the bz2 stuff in just the set_mem() function.

Quoted 8 lines

Quoted 3 lines

. check is always true in callers, and I'm not sure why you'd have it zero.

The magic number checking seems fragile - I'm assuming it might be necessary to force the stream as compressed at some point. Since we are maintaining ABI for this library (and these functions), seems better to be safe.

Do policy files not have a magic value, then?

You can also (for bz2)
check that the next value is between 1 and 9 (it's the compression ratio).

I assume this means you'd rely on anything ending in ".bz2" being
compressed, and not otherwise ... do we always have a filename?

Quoted 10 lines

Quoted 9 lines

. All code paths have:

if (set_foo_bz2() == FAILED)
set_foo();

...which tells me set_foo_bz2() should do that ... in fact it seems sane to just change set_foo() to check of bz2ness and do the right thing, without having to alter the callers.

Quoted 2 lines

Note my comments with the original patch - this isn't possible because set_foo() has a void return and we want to maintain binary compatibility.

Right, but as I said the error paths always just try again without
compression ... so why not just try the compression at the start of the set_foo() code. You get the same behaviour.

Review

Quoted 8 lines

Quoted 2 lines

I assume the only reason you went with bzip2 over gzip is the "have to
init yourself in the set_mem case"?

No - just better compression.

[kmacmill@localhost ~]$ ls -l base.pp.*

(quoted diff) +0 -2

-rw-r--r-- 1 kmacmill kmacmill  86379 Jan  9 10:50 base.pp.bz2
-rw-r--r-- 1 kmacmill kmacmill 167382 Jan  9 10:50 base.pp.gz

Wow ... that's better than usual. Do you have the same difference for
smaller modules?

Quoted 1 line · James Antill

Do policy files not have a magic value, then?

They do, but there is no real restriction that these policy file things get used for files containing policy. Currently they are used for a variety of file types and I would hate to hard code a list valid file types into this function.

Quoted 3 lines

You can also (for bz2)
check that the next value is between 1 and 9 (it's the compression ratio).

Ok. Could this be used for sizing the buffer in the memory case?

Quoted 4 lines

Right, but as I said the error paths always just try again without
compression ... so why not just try the compression at the start of the set_foo() code. You get the same behaviour.

It is not about returning information about the compression. It is because the compression routines have other error paths (failure to load libbz2, memory allocation, etc.). There is no good way to indicate those errors without changing the prototypes. Even if we didn't change the prototypes, it is valid to not check the current functions for error, so we can't change them in any way that has potential error paths.

 I assume the only reason you went with bzip2 over gzip is the "have to init yourself in the set_mem case"? I've done that before[1], so I can help you get that bit done if you want ... this will drop CPU/memory/dependency requirements (although expecting all Linux to have libbz now isn't a big deal, IMO).

Uncompressed
------------

[root@localhost modules]# time semodule -b
/usr/share/selinux/strict/base.pp

real    0m15.849s
user    0m14.791s
sys     0m0.930s

[root@localhost nobz-modules]# time semodule -i *.pp

real    0m15.447s
user    0m14.287s
sys     0m0.997s

Compressed
----------

[root@localhost modules]# time semodule -b /root/base.pp.bz2

real    0m16.117s
user    0m14.729s
sys     0m1.022s

[root@localhost modules]# time semodule -i /root/modules/*.bz2

real    0m18.529s
user    0m17.110s
sys     0m1.314s

Quoted 3 lines · Karl MacMillan

Quoted 1 line · James Antill

Do policy files not have a magic value, then?

Quoted 4 lines

They do, but there is no real restriction that these policy file things get used for files containing policy. Currently they are used for a variety of file types and I would hate to hard code a list valid file types into this function.

I don't think I'm intelligent enough to understand this sentence :).
What I meant was if they have magic values, they'll never clash so it's always ok to do the check, no?

Or in the other direction, if you can't differentiate on magic value or
the filename how can any piece of code tell whether it should decompress it or treat it as raw data?

Quoted 5 lines

Quoted 3 lines

You can also (for bz2)
check that the next value is between 1 and 9 (it's the compression ratio).

Ok. Could this be used for sizing the buffer in the memory case?

No, it's just the "how hard did you want to try" value. So something
compressed with "bzip2 -1" will have a '1' and likewise "bzip2 -9" will have a '9' after the magic.

Quoted 11 lines

Quoted 4 lines

Right, but as I said the error paths always just try again without
compression ... so why not just try the compression at the start of the set_foo() code. You get the same behaviour.

It is not about returning information about the compression. It is because the compression routines have other error paths (failure to load libbz2, memory allocation, etc.). There is no good way to indicate those errors without changing the prototypes. Even if we didn't change the prototypes, it is valid to not check the current functions for error, so we can't change them in any way that has potential error paths.

Yes, I know that ... but there isn't a difference in the return value
between "bz2_init() failed" and "is_bz2_file() returned NO". So all the callers just assume the later for all errors, if that's the case we might as well combine it back into set_foo().

Quoted 5 lines · James Antill

I assume the only reason you went with bzip2 over gzip is the "have to
init yourself in the set_mem case"? I've done that before[1], so I can help you get that bit done if you want ... this will drop CPU/memory/dependency requirements (although expecting all Linux to have libbz now isn't a big deal, IMO).

Given that the vast majority of new machines now are AMD64 part of the CPU requirement will be due to bzip2 and gzip not being optimised for AMD64. gzip has i386 assembler optimisation but no AMD64 assembler and runs more slowly on AMD64 because of it (my tests show that on RHEL4 the i386 copy of gzip outperforms the AMD64 version on Opteron machines).

If you compare the AMD64 compiled version of gzip (IE the library) with bzip2 the difference in CPU time is a lot smaller than it is when comparing the i386 versions.

Of course it probably wouldn't be difficult for someone to write some AMD64 assembler code for gzip or bzip2 to change things.

In regard to the following, I think that the 15 seconds for uncompressed operation is the problem not the 1-3 seconds that are added. Is there any chance of optimising the other operations of semodule? If we could get a 10% improvement in the base functionality then "semodule -b" with compression would be expected to give the same performance as currently, if we could get a 20% improvement then "semodule -i" would give the current performance too.