libsparse/sparse.c

   1 /*
   2  * Copyright (C) 2012 The Android Open Source Project
   3  *
   4  * Licensed under the Apache License, Version 2.0 (the "License");
   5  * you may not use this file except in compliance with the License.
   6  * You may obtain a copy of the License at
   7  *
   8  *      http://www.apache.org/licenses/LICENSE-2.0
   9  *
  10  * Unless required by applicable law or agreed to in writing, software
  11  * distributed under the License is distributed on an "AS IS" BASIS,
  12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  13  * See the License for the specific language governing permissions and
  14  * limitations under the License.
  15  */
  16
  17 #include <assert.h>
  18 #include <stdlib.h>
  19
  20 #include <sparse/sparse.h>
  21
  22 #include "defs.h"
  23 #include "sparse_file.h"
  24
  25 #include "output_file.h"
  26 #include "backed_block.h"
  27 #include "sparse_defs.h"
  28 #include "sparse_format.h"
  29
  30 struct sparse_file *sparse_file_new(unsigned int block_size, int64_t len)
  31 {
  32         struct sparse_file *s = calloc(sizeof(struct sparse_file), 1);
  33         if (!s) {
  34                 return NULL;
  35         }
  36
  37         s->backed_block_list = backed_block_list_new(block_size);
  38         if (!s->backed_block_list) {
  39                 free(s);
  40                 return NULL;
  41         }
  42
  43         s->block_size = block_size;
  44         s->len = len;
  45
  46         return s;
  47 }
  48
  49 void sparse_file_destroy(struct sparse_file *s)
  50 {
  51         backed_block_list_destroy(s->backed_block_list);
  52         free(s);
  53 }
  54
  55 int sparse_file_add_data(struct sparse_file *s,
  56                 void *data, unsigned int len, unsigned int block)
  57 {
  58         return backed_block_add_data(s->backed_block_list, data, len, block);
  59 }
  60
  61 int sparse_file_add_fill(struct sparse_file *s,
  62                 uint32_t fill_val, unsigned int len, unsigned int block)
  63 {
  64         return backed_block_add_fill(s->backed_block_list, fill_val, len, block);
  65 }
  66
  67 int sparse_file_add_file(struct sparse_file *s,
  68                 const char *filename, int64_t file_offset, unsigned int len,
  69                 unsigned int block)
  70 {
  71         return backed_block_add_file(s->backed_block_list, filename, file_offset,
  72                         len, block);
  73 }
  74
  75 int sparse_file_add_fd(struct sparse_file *s,
  76                 int fd, int64_t file_offset, unsigned int len, unsigned int block)
  77 {
  78         return backed_block_add_fd(s->backed_block_list, fd, file_offset,
  79                         len, block);
  80 }
  81 unsigned int sparse_count_chunks(struct sparse_file *s)
  82 {
  83         struct backed_block *bb;
  84         unsigned int last_block = 0;
  85         unsigned int chunks = 0;
  86
  87         for (bb = backed_block_iter_new(s->backed_block_list); bb;
  88                         bb = backed_block_iter_next(bb)) {
  89                 if (backed_block_block(bb) > last_block) {
  90                         /* If there is a gap between chunks, add a skip chunk */
  91                         chunks++;
  92                 }
  93                 chunks++;
  94                 last_block = backed_block_block(bb) +
  95                                 DIV_ROUND_UP(backed_block_len(bb), s->block_size);
  96         }
  97         if (last_block < DIV_ROUND_UP(s->len, s->block_size)) {
  98                 chunks++;
  99         }
 100
 101         return chunks;
 102 }
 103
 104 static int sparse_file_write_block(struct output_file *out,
 105                 struct backed_block *bb)
 106 {
 107         int ret = -EINVAL;
 108
 109         switch (backed_block_type(bb)) {
 110         case BACKED_BLOCK_DATA:
 111                 ret = write_data_chunk(out, backed_block_len(bb), backed_block_data(bb));
 112                 break;
 113         case BACKED_BLOCK_FILE:
 114                 ret = write_file_chunk(out, backed_block_len(bb),
 115                                        backed_block_filename(bb),
 116                                        backed_block_file_offset(bb));
 117                 break;
 118         case BACKED_BLOCK_FD:
 119                 ret = write_fd_chunk(out, backed_block_len(bb),
 120                                      backed_block_fd(bb),
 121                                      backed_block_file_offset(bb));
 122                 break;
 123         case BACKED_BLOCK_FILL:
 124                 ret = write_fill_chunk(out, backed_block_len(bb),
 125                                        backed_block_fill_val(bb));
 126                 break;
 127         }
 128
 129         return ret;
 130 }
 131
 132 static int write_all_blocks(struct sparse_file *s, struct output_file *out)
 133 {
 134         struct backed_block *bb;
 135         unsigned int last_block = 0;
 136         int64_t pad;
 137         int ret = 0;
 138
 139         for (bb = backed_block_iter_new(s->backed_block_list); bb;
 140                         bb = backed_block_iter_next(bb)) {
 141                 if (backed_block_block(bb) > last_block) {
 142                         unsigned int blocks = backed_block_block(bb) - last_block;
 143                         write_skip_chunk(out, (int64_t)blocks * s->block_size);
 144                 }
 145                 ret = sparse_file_write_block(out, bb);
 146                 if (ret)
 147                         return ret;
 148                 last_block = backed_block_block(bb) +
 149                                 DIV_ROUND_UP(backed_block_len(bb), s->block_size);
 150         }
 151
 152         pad = s->len - (int64_t)last_block * s->block_size;
 153         assert(pad >= 0);
 154         if (pad > 0) {
 155                 write_skip_chunk(out, pad);
 156         }
 157
 158         return 0;
 159 }
 160
 161 int sparse_file_write(struct sparse_file *s, int fd, bool gz, bool sparse,
 162                 bool crc)
 163 {
 164         int ret;
 165         int chunks;
 166         struct output_file *out;
 167
 168         chunks = sparse_count_chunks(s);
 169         out = output_file_open_fd(fd, s->block_size, s->len, gz, sparse, chunks, crc);
 170
 171         if (!out)
 172                 return -ENOMEM;
 173
 174         ret = write_all_blocks(s, out);
 175
 176         output_file_close(out);
 177
 178         return ret;
 179 }
 180
 181 int sparse_file_callback(struct sparse_file *s, bool sparse, bool crc,
 182                 int (*write)(void *priv, const void *data, int len), void *priv)
 183 {
 184         int ret;
 185         int chunks;
 186         struct output_file *out;
 187
 188         chunks = sparse_count_chunks(s);
 189         out = output_file_open_callback(write, priv, s->block_size, s->len, false,
 190                         sparse, chunks, crc);
 191
 192         if (!out)
 193                 return -ENOMEM;
 194
 195         ret = write_all_blocks(s, out);
 196
 197         output_file_close(out);
 198
 199         return ret;
 200 }
 201
 202 static int out_counter_write(void *priv, const void *data __unused, int len)
 203 {
 204         int64_t *count = priv;
 205         *count += len;
 206         return 0;
 207 }
 208
 209 int64_t sparse_file_len(struct sparse_file *s, bool sparse, bool crc)
 210 {
 211         int ret;
 212         int chunks = sparse_count_chunks(s);
 213         int64_t count = 0;
 214         struct output_file *out;
 215
 216         out = output_file_open_callback(out_counter_write, &count,
 217                         s->block_size, s->len, false, sparse, chunks, crc);
 218         if (!out) {
 219                 return -1;
 220         }
 221
 222         ret = write_all_blocks(s, out);
 223
 224         output_file_close(out);
 225
 226         if (ret < 0) {
 227                 return -1;
 228         }
 229
 230         return count;
 231 }
 232
 233 static struct backed_block *move_chunks_up_to_len(struct sparse_file *from,
 234                 struct sparse_file *to, unsigned int len)
 235 {
 236         int64_t count = 0;
 237         struct output_file *out_counter;
 238         struct backed_block *last_bb = NULL;
 239         struct backed_block *bb;
 240         struct backed_block *start;
 241         int64_t file_len = 0;
 242         int ret;
 243
 244         /*
 245          * overhead is sparse file header, initial skip chunk, split chunk, end
 246          * skip chunk, and crc chunk.
 247          */
 248         int overhead = sizeof(sparse_header_t) + 4 * sizeof(chunk_header_t) +
 249                         sizeof(uint32_t);
 250         len -= overhead;
 251
 252         start = backed_block_iter_new(from->backed_block_list);
 253         out_counter = output_file_open_callback(out_counter_write, &count,
 254                         to->block_size, to->len, false, true, 0, false);
 255         if (!out_counter) {
 256                 return NULL;
 257         }
 258
 259         for (bb = start; bb; bb = backed_block_iter_next(bb)) {
 260                 count = 0;
 261                 /* will call out_counter_write to update count */
 262                 ret = sparse_file_write_block(out_counter, bb);
 263                 if (ret) {
 264                         bb = NULL;
 265                         goto out;
 266                 }
 267                 if (file_len + count > len) {
 268                         /*
 269                          * If the remaining available size is more than 1/8th of the
 270                          * requested size, split the chunk.  Results in sparse files that
 271                          * are at least 7/8ths of the requested size
 272                          */
 273                         if (!last_bb || (len - file_len > (len / 8))) {
 274                                 backed_block_split(from->backed_block_list, bb, len - file_len);
 275                                 last_bb = bb;
 276                         }
 277                         goto move;
 278                 }
 279                 file_len += count;
 280                 last_bb = bb;
 281         }
 282
 283 move:
 284         backed_block_list_move(from->backed_block_list,
 285                 to->backed_block_list, start, last_bb);
 286
 287 out:
 288         output_file_close(out_counter);
 289
 290         return bb;
 291 }
 292
 293 int sparse_file_resparse(struct sparse_file *in_s, unsigned int max_len,
 294                 struct sparse_file **out_s, int out_s_count)
 295 {
 296         struct backed_block *bb;
 297         struct sparse_file *s;
 298         struct sparse_file *tmp;
 299         int c = 0;
 300
 301         tmp = sparse_file_new(in_s->block_size, in_s->len);
 302         if (!tmp) {
 303                 return -ENOMEM;
 304         }
 305
 306         do {
 307                 s = sparse_file_new(in_s->block_size, in_s->len);
 308
 309                 bb = move_chunks_up_to_len(in_s, s, max_len);
 310
 311                 if (c < out_s_count) {
 312                         out_s[c] = s;
 313                 } else {
 314                         backed_block_list_move(s->backed_block_list, tmp->backed_block_list,
 315                                         NULL, NULL);
 316                         sparse_file_destroy(s);
 317                 }
 318                 c++;
 319         } while (bb);
 320
 321         backed_block_list_move(tmp->backed_block_list, in_s->backed_block_list,
 322                         NULL, NULL);
 323
 324         sparse_file_destroy(tmp);
 325
 326         return c;
 327 }
 328
 329 void sparse_file_verbose(struct sparse_file *s)
 330 {
 331         s->verbose = true;
 332 }