~bzr-pqm/bzr/bzr.dev

Committer: Canonical.com Patch Queue Manager
Date: 2011-05-16 17:33:27 UTC
mfrom: (5755.2.10 2.4-max-entries-gc-602614)
Revision ID: pqm@pqm.ubuntu.com-20110516173327-5ehst0ttceohsf5w

(jameinel) Add bzr.groupcompress.max_bytes_to_index to limit peak memory
when delta-compressing large files (bug #602614) (John A Meinel)

files modified:
bzrlib/_groupcompress_pyx.pyx

bzrlib/delta.h

bzrlib/diff-delta.c

bzrlib/groupcompress.py

bzrlib/tests/test__groupcompress.py

bzrlib/tests/test_groupcompress.py

doc/en/release-notes/bzr-2.4.txt

Show diffs side-by-side

added added

removed removed

bzrlib/diff-delta.c

376

delta_result

377

create_delta_index(const struct source_info *src,

378

struct delta_index *old,

379

struct delta_index **fresh)

379

struct delta_index **fresh,

380

int max_bytes_to_index)

380

381

{

381

382

unsigned int i, hsize, hmask, num_entries, prev_val, *hash_count;

382

unsigned int total_num_entries;

383

unsigned int total_num_entries, stride, max_entries;

383

384

const unsigned char *data, *buffer;

384

385

struct delta_index *index;

385

386

struct unpacked_index_entry *entry, **hash;

391

392

buffer = src->buf;

392

393

394

/* Determine index hash size. Note that indexing skips the

394

first byte to allow for optimizing the Rabin's polynomial

395

initialization in create_delta(). */

395

first byte so we subtract 1 to get the edge cases right.

396

397

stride = RABIN_WINDOW;

396

398

num_entries = (src->size - 1) / RABIN_WINDOW;

399

if (max_bytes_to_index > 0) {

400

max_entries = (unsigned int) (max_bytes_to_index / RABIN_WINDOW);

401

if (num_entries > max_entries) {

402

/* Limit the max number of matching entries. This reduces the 'best'

403

* possible match, but means we don't consume all of ram.

404

405

num_entries = max_entries;

406

stride = (src->size - 1) / num_entries;

407

}

408

}

397

409

if (old != NULL)

398

410

total_num_entries = num_entries + old->num_entries;

399

411

else

428

440

429

441

/* then populate the index for the new data */

430

442

prev_val = ~0;

431

for (data = buffer + num_entries * RABIN_WINDOW - RABIN_WINDOW;

443

for (data = buffer + num_entries * stride - RABIN_WINDOW;

432

444

data >= buffer;

433

data -= RABIN_WINDOW) {

445

data -= stride) {

434

446

unsigned int val = 0;

435

447

for (i = 1; i <= RABIN_WINDOW; i++)

436

448

val = ((val << 8) | data[i]) ^ T[val >> RABIN_SHIFT];

476

488

unsigned int hsize)

477

489

{

478

490

unsigned int hash_offset, hmask, memsize;

479

struct index_entry *entry, *last_entry;

491

struct index_entry *entry;

480

492

struct index_entry_linked_list *out_entry, **hash;

481

493

void *mem;

482

494

496

508

/* We know that entries are in the order we want in the output, but they

497

509

* aren't "grouped" by hash bucket yet.

498

510

499

last_entry = entries + num_entries;

500

511

for (entry = entries + num_entries - 1; entry >= entries; --entry) {

501

512

hash_offset = entry->val & hmask;

502

513

out_entry->p_entry = entry;

521

532

unsigned int i, j, hsize, hmask, total_num_entries;

522

533

struct delta_index *index;

523

534

struct index_entry *entry, *packed_entry, **packed_hash;

524

struct index_entry *last_entry, null_entry = {0};

535

struct index_entry null_entry = {0};

525

536

void *mem;

526

537

unsigned long memsize;

527

538

struct index_entry_linked_list *unpacked_entry, **mini_hash;

572

583

free(index);

573

584

return NULL;

574

585

}

575

last_entry = entries + num_entries;

576

586

for (i = 0; i < hsize; i++) {

577

587

578

588

* Coalesce all entries belonging in one hash bucket

1100

1110

return DELTA_OK;

1101

1111

}

1102

1112

1113

1114

int

1115

get_entry_summary(const struct delta_index *index, int pos,

1116

unsigned int *text_offset, unsigned int *hash_val)

1117

{

1118

int hsize;

1119

const struct index_entry *entry;

1120

const struct index_entry *start_of_entries;

1121

unsigned int offset;

1122

if (pos < 0 || text_offset == NULL || hash_val == NULL

1123

|| index == NULL)

1124

{

1125

return 0;

1126

}

1127

hsize = index->hash_mask + 1;

1128

start_of_entries = (struct index_entry *)(((struct index_entry **)index->hash) + (hsize + 1));

1129

entry = start_of_entries + pos;

1130

if (entry > index->last_entry) {

1131

return 0;

1132

}

1133

if (entry->ptr == NULL) {

1134

*text_offset = 0;

1135

*hash_val = 0;

1136

} else {

1137

offset = entry->src->agg_offset;

1138

offset += (entry->ptr - ((unsigned char *)entry->src->buf));

1139

*text_offset = offset;

1140

*hash_val = entry->val;

1141

}

1142

return 1;

1143

}

1144

1145

1146

int

1147

get_hash_offset(const struct delta_index *index, int pos,

1148

unsigned int *entry_offset)

1149

{

1150

int hsize;

1151

const struct index_entry *entry;

1152

const struct index_entry *start_of_entries;

1153

if (pos < 0 || index == NULL || entry_offset == NULL)

1154

{

1155

return 0;

1156

}

1157

hsize = index->hash_mask + 1;

1158

start_of_entries = (struct index_entry *)(((struct index_entry **)index->hash) + (hsize + 1));

1159

if (pos >= hsize) {

1160

return 0;

1161

}

1162

entry = index->hash[pos];

1163

if (entry == NULL) {

1164

*entry_offset = -1;

1165

} else {

1166

*entry_offset = (entry - start_of_entries);

1167

}

1168

return 1;

1169

}

1170

1171

1172

unsigned int

1173

rabin_hash(const unsigned char *data)

1174

{

1175

int i;

1176

unsigned int val = 0;

1177

for (i = 0; i < RABIN_WINDOW; i++)

1178

val = ((val << 8) | data[i]) ^ T[val >> RABIN_SHIFT];

1179

return val;

1180

}

1181

1103

1182

/* vim: et ts=4 sw=4 sts=4

1104

1183

Older »