source.dussan.org Git - jgit.git/blob

1 /*

3 * and other copyright owners as documented in the project's IP log.

4 *

5 * This program and the accompanying materials are made available

6 * under the terms of the Eclipse Distribution License v1.0 which

7 * accompanies this distribution, is reproduced below, and is

8 * available at http://www.eclipse.org/org/documents/edl-v10.php

9 *

11 *

12 * Redistribution and use in source and binary forms, with or

13 * without modification, are permitted provided that the following

14 * conditions are met:

15 *

16 * - Redistributions of source code must retain the above copyright

17 * notice, this list of conditions and the following disclaimer.

18 *

19 * - Redistributions in binary form must reproduce the above

20 * copyright notice, this list of conditions and the following

21 * disclaimer in the documentation and/or other materials provided

22 * with the distribution.

23 *

24 * - Neither the name of the Eclipse Foundation, Inc. nor the

25 * names of its contributors may be used to endorse or promote

26 * products derived from this software without specific prior

27 * written permission.

28 *

29 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND

30 * CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES,

31 * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES

32 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE

33 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR

34 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,

35 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT

36 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;

37 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER

38 * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,

39 * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)

40 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF

41 * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

42 */

43

44 package org.eclipse.jgit.storage.file;

45

46 import java.io.BufferedReader;

47 import java.io.File;

48 import java.io.FileInputStream;

49 import java.io.FileNotFoundException;

50 import java.io.FileReader;

51 import java.io.IOException;

52 import java.text.MessageFormat;

53 import java.util.ArrayList;

54 import java.util.Arrays;

55 import java.util.Collection;

56 import java.util.Collections;

57 import java.util.HashMap;

58 import java.util.HashSet;

59 import java.util.List;

60 import java.util.Map;

61 import java.util.Set;

62 import java.util.concurrent.atomic.AtomicReference;

63

64 import org.eclipse.jgit.JGitText;

65 import org.eclipse.jgit.errors.PackMismatchException;

66 import org.eclipse.jgit.lib.AbbreviatedObjectId;

67 import org.eclipse.jgit.lib.AnyObjectId;

68 import org.eclipse.jgit.lib.Config;

69 import org.eclipse.jgit.lib.Constants;

70 import org.eclipse.jgit.lib.ObjectDatabase;

71 import org.eclipse.jgit.lib.ObjectId;

72 import org.eclipse.jgit.lib.ObjectInserter;

73 import org.eclipse.jgit.lib.ObjectLoader;

74 import org.eclipse.jgit.lib.RepositoryCache;

75 import org.eclipse.jgit.lib.RepositoryCache.FileKey;

76 import org.eclipse.jgit.storage.pack.ObjectToPack;

77 import org.eclipse.jgit.storage.pack.PackWriter;

78 import org.eclipse.jgit.util.FS;

79

80 /**

81 * Traditional file system based {@link ObjectDatabase}.

82 * <p>

83 * This is the classical object database representation for a Git repository,

84 * where objects are stored loose by hashing them into directories by their

85 * {@link ObjectId}, or are stored in compressed containers known as

86 * {@link PackFile}s.

87 * <p>

88 * Optionally an object database can reference one or more alternates; other

89 * ObjectDatabase instances that are searched in addition to the current

90 * database.

91 * <p>

92 * Databases are divided into two halves: a half that is considered to be fast

93 * to search (the {@code PackFile}s), and a half that is considered to be slow

94 * to search (loose objects). When alternates are present the fast half is fully

95 * searched (recursively through all alternates) before the slow half is

96 * considered.

97 */

98 public class ObjectDirectory extends FileObjectDatabase {

99 private static final PackList NO_PACKS = new PackList(-1, -1, new PackFile[0]);

100

101 /** Maximum number of candidates offered as resolutions of abbreviation. */

102 private static final int RESOLVE_ABBREV_LIMIT = 256;

103

104 private final Config config;

105

106 private final File objects;

107

108 private final File infoDirectory;

109

110 private final File packDirectory;

111

112 private final File alternatesFile;

113

114 private final AtomicReference<PackList> packList;

115

116 private final FS fs;

117

118 private final AtomicReference<AlternateHandle[]> alternates;

119

120 private final UnpackedObjectCache unpackedObjectCache;

121

122 /**

123 * Initialize a reference to an on-disk object directory.

124 *

125 * @param cfg

126 * configuration this directory consults for write settings.

127 * @param dir

128 * the location of the <code>objects</code> directory.

129 * @param alternatePaths

130 * a list of alternate object directories

131 * @param fs

132 * the file system abstraction which will be necessary to perform

133 * certain file system operations.

134 * @throws IOException

135 * an alternate object cannot be opened.

136 */

137 public ObjectDirectory(final Config cfg, final File dir,

138 File[] alternatePaths, FS fs) throws IOException {

139 config = cfg;

140 objects = dir;

141 infoDirectory = new File(objects, "info");

142 packDirectory = new File(objects, "pack");

143 alternatesFile = new File(infoDirectory, "alternates");

144 packList = new AtomicReference<PackList>(NO_PACKS);

145 unpackedObjectCache = new UnpackedObjectCache();

146 this.fs = fs;

147

148 alternates = new AtomicReference<AlternateHandle[]>();

149 if (alternatePaths != null) {

150 AlternateHandle[] alt;

151

152 alt = new AlternateHandle[alternatePaths.length];

153 for (int i = 0; i < alternatePaths.length; i++)

154 alt[i] = openAlternate(alternatePaths[i]);

155 alternates.set(alt);

156 }

157 }

158

159 /**

160 * @return the location of the <code>objects</code> directory.

161 */

162 public final File getDirectory() {

163 return objects;

164 }

165

166 @Override

167 public boolean exists() {

168 return objects.exists();

169 }

170

171 @Override

172 public void create() throws IOException {

173 objects.mkdirs();

174 infoDirectory.mkdir();

175 packDirectory.mkdir();

176 }

177

178 @Override

179 public ObjectInserter newInserter() {

180 return new ObjectDirectoryInserter(this, config);

181 }

182

183 @Override

184 public void close() {

185 unpackedObjectCache.clear();

186

187 final PackList packs = packList.get();

188 packList.set(NO_PACKS);

189 for (final PackFile p : packs.packs)

190 p.close();

191

192 // Fully close all loaded alternates and clear the alternate list.

193 AlternateHandle[] alt = alternates.get();

194 if (alt != null) {

195 alternates.set(null);

196 for(final AlternateHandle od : alt)

197 od.close();

198 }

199 }

200

201 /**

202 * Compute the location of a loose object file.

203 *

204 * @param objectId

205 * identity of the loose object to map to the directory.

206 * @return location of the object, if it were to exist as a loose object.

207 */

208 public File fileFor(final AnyObjectId objectId) {

209 return fileFor(objectId.name());

210 }

211

212 private File fileFor(final String objectName) {

213 final String d = objectName.substring(0, 2);

214 final String f = objectName.substring(2);

215 return new File(new File(objects, d), f);

216 }

217

218 /**

219 * @return unmodifiable collection of all known pack files local to this

220 * directory. Most recent packs are presented first. Packs most

221 * likely to contain more recent objects appear before packs

222 * containing objects referenced by commits further back in the

223 * history of the repository.

224 */

225 public Collection<PackFile> getPacks() {

226 final PackFile[] packs = packList.get().packs;

227 return Collections.unmodifiableCollection(Arrays.asList(packs));

228 }

229

230 /**

231 * Add a single existing pack to the list of available pack files.

232 *

233 * @param pack

234 * path of the pack file to open.

235 * @param idx

236 * path of the corresponding index file.

237 * @throws IOException

238 * index file could not be opened, read, or is not recognized as

239 * a Git pack file index.

240 */

241 public void openPack(final File pack, final File idx) throws IOException {

242 final String p = pack.getName();

243 final String i = idx.getName();

244

245 if (p.length() != 50 || !p.startsWith("pack-") || !p.endsWith(".pack"))

246 throw new IOException(MessageFormat.format(JGitText.get().notAValidPack, pack));

247

248 if (i.length() != 49 || !i.startsWith("pack-") || !i.endsWith(".idx"))

249 throw new IOException(MessageFormat.format(JGitText.get().notAValidPack, idx));

250

251 if (!p.substring(0, 45).equals(i.substring(0, 45)))

252 throw new IOException(MessageFormat.format(JGitText.get().packDoesNotMatchIndex, pack));

253

254 insertPack(new PackFile(idx, pack));

255 }

256

257 @Override

258 public String toString() {

259 return "ObjectDirectory[" + getDirectory() + "]";

260 }

261

262 boolean hasObject1(final AnyObjectId objectId) {

263 if (unpackedObjectCache.isUnpacked(objectId))

264 return true;

265 for (final PackFile p : packList.get().packs) {

266 try {

267 if (p.hasObject(objectId)) {

268 return true;

269 }

270 } catch (IOException e) {

271 // The hasObject call should have only touched the index,

272 // so any failure here indicates the index is unreadable

273 // by this process, and the pack is likewise not readable.

274 //

275 removePack(p);

276 continue;

277 }

278 }

279 return false;

280 }

281

282 void resolve(Set<ObjectId> matches, AbbreviatedObjectId id)

283 throws IOException {

284 // Go through the packs once. If we didn't find any resolutions

285 // scan for new packs and check once more.

286 //

287 int oldSize = matches.size();

288 PackList pList = packList.get();

289 for (;;) {

290 for (PackFile p : pList.packs) {

291 try {

292 p.resolve(matches, id, RESOLVE_ABBREV_LIMIT);

293 } catch (IOException e) {

294 // Assume the pack is corrupted.

295 //

296 removePack(p);

297 }

298 if (matches.size() > RESOLVE_ABBREV_LIMIT)

299 return;

300 }

301 if (matches.size() == oldSize) {

302 PackList nList = scanPacks(pList);

303 if (nList == pList || nList.packs.length == 0)

304 break;

305 pList = nList;

306 continue;

307 }

308 break;

309 }

310

311 String fanOut = id.name().substring(0, 2);

312 String[] entries = new File(getDirectory(), fanOut).list();

313 if (entries != null) {

314 for (String e : entries) {

315 if (e.length() != Constants.OBJECT_ID_STRING_LENGTH - 2)

316 continue;

317 try {

318 ObjectId entId = ObjectId.fromString(fanOut + e);

319 if (id.prefixCompare(entId) == 0)

320 matches.add(entId);

321 } catch (IllegalArgumentException notId) {

322 continue;

323 }

324 if (matches.size() > RESOLVE_ABBREV_LIMIT)

325 return;

326 }

327 }

328

329 for (AlternateHandle alt : myAlternates()) {

330 alt.db.resolve(matches, id);

331 if (matches.size() > RESOLVE_ABBREV_LIMIT)

332 return;

333 }

334 }

335

336 ObjectLoader openObject1(final WindowCursor curs,

337 final AnyObjectId objectId) throws IOException {

338 if (unpackedObjectCache.isUnpacked(objectId)) {

339 ObjectLoader ldr = openObject2(curs, objectId.name(), objectId);

340 if (ldr != null)

341 return ldr;

342 else

343 unpackedObjectCache.remove(objectId);

344 }

345

346 PackList pList = packList.get();

347 SEARCH: for (;;) {

348 for (final PackFile p : pList.packs) {

349 try {

350 final ObjectLoader ldr = p.get(curs, objectId);

351 if (ldr != null)

352 return ldr;

353 } catch (PackMismatchException e) {

354 // Pack was modified; refresh the entire pack list.

355 //

356 pList = scanPacks(pList);

357 continue SEARCH;

358 } catch (IOException e) {

359 // Assume the pack is corrupted.

360 //

361 removePack(p);

362 }

363 }

364 return null;

365 }

366 }

367

368 long getObjectSize1(final WindowCursor curs, final AnyObjectId objectId)

369 throws IOException {

370 PackList pList = packList.get();

371 SEARCH: for (;;) {

372 for (final PackFile p : pList.packs) {

373 try {

374 long sz = p.getObjectSize(curs, objectId);

375 if (0 <= sz)

376 return sz;

377 } catch (PackMismatchException e) {

378 // Pack was modified; refresh the entire pack list.

379 //

380 pList = scanPacks(pList);

381 continue SEARCH;

382 } catch (IOException e) {

383 // Assume the pack is corrupted.

384 //

385 removePack(p);

386 }

387 }

388 return -1;

389 }

390 }

391

392 @Override

393 long getObjectSize2(WindowCursor curs, String objectName,

394 AnyObjectId objectId) throws IOException {

395 try {

396 File path = fileFor(objectName);

397 FileInputStream in = new FileInputStream(path);

398 try {

399 return UnpackedObject.getSize(in, objectId, curs);

400 } finally {

401 in.close();

402 }

403 } catch (FileNotFoundException noFile) {

404 return -1;

405 }

406 }

407

408 @Override

409 void selectObjectRepresentation(PackWriter packer, ObjectToPack otp,

410 WindowCursor curs) throws IOException {

411 PackList pList = packList.get();

412 SEARCH: for (;;) {

413 for (final PackFile p : pList.packs) {

414 try {

415 LocalObjectRepresentation rep = p.representation(curs, otp);

416 if (rep != null)

417 packer.select(otp, rep);

418 } catch (PackMismatchException e) {

419 // Pack was modified; refresh the entire pack list.

420 //

421 pList = scanPacks(pList);

422 continue SEARCH;

423 } catch (IOException e) {

424 // Assume the pack is corrupted.

425 //

426 removePack(p);

427 }

428 }

429 break SEARCH;

430 }

431

432 for (AlternateHandle h : myAlternates())

433 h.db.selectObjectRepresentation(packer, otp, curs);

434 }

435

436 boolean hasObject2(final String objectName) {

437 return fileFor(objectName).exists();

438 }

439

440 ObjectLoader openObject2(final WindowCursor curs,

441 final String objectName, final AnyObjectId objectId)

442 throws IOException {

443 try {

444 File path = fileFor(objectName);

445 FileInputStream in = new FileInputStream(path);

446 try {

447 unpackedObjectCache.add(objectId);

448 return UnpackedObject.open(in, path, objectId, curs);

449 } finally {

450 in.close();

451 }

452 } catch (FileNotFoundException noFile) {

453 unpackedObjectCache.remove(objectId);

454 return null;

455 }

456 }

457

458 void addUnpackedObject(ObjectId id) {

459 unpackedObjectCache.add(id);

460 }

461

462 boolean tryAgain1() {

463 final PackList old = packList.get();

464 if (old.tryAgain(packDirectory.lastModified()))

465 return old != scanPacks(old);

466 return false;

467 }

468

469 private void insertPack(final PackFile pf) {

470 PackList o, n;

471 do {

472 o = packList.get();

473

474 // If the pack in question is already present in the list

475 // (picked up by a concurrent thread that did a scan?) we

476 // do not want to insert it a second time.

477 //

478 final PackFile[] oldList = o.packs;

479 final String name = pf.getPackFile().getName();

480 for (PackFile p : oldList) {

481 if (PackFile.SORT.compare(pf, p) < 0)

482 break;

483 if (name.equals(p.getPackFile().getName()))

484 return;

485 }

486

487 final PackFile[] newList = new PackFile[1 + oldList.length];

488 newList[0] = pf;

489 System.arraycopy(oldList, 0, newList, 1, oldList.length);

490 n = new PackList(o.lastRead, o.lastModified, newList);

491 } while (!packList.compareAndSet(o, n));

492 }

493

494 private void removePack(final PackFile deadPack) {

495 PackList o, n;

496 do {

497 o = packList.get();

498

499 final PackFile[] oldList = o.packs;

500 final int j = indexOf(oldList, deadPack);

501 if (j < 0)

502 break;

503

504 final PackFile[] newList = new PackFile[oldList.length - 1];

505 System.arraycopy(oldList, 0, newList, 0, j);

506 System.arraycopy(oldList, j + 1, newList, j, newList.length - j);

507 n = new PackList(o.lastRead, o.lastModified, newList);

508 } while (!packList.compareAndSet(o, n));

509 deadPack.close();

510 }

511

512 private static int indexOf(final PackFile[] list, final PackFile pack) {

513 for (int i = 0; i < list.length; i++) {

514 if (list[i] == pack)

515 return i;

516 }

517 return -1;

518 }

519

520 private PackList scanPacks(final PackList original) {

521 synchronized (packList) {

522 PackList o, n;

523 do {

524 o = packList.get();

525 if (o != original) {

526 // Another thread did the scan for us, while we

527 // were blocked on the monitor above.

528 //

529 return o;

530 }

531 n = scanPacksImpl(o);

532 if (n == o)

533 return n;

534 } while (!packList.compareAndSet(o, n));

535 return n;

536 }

537 }

538

539 private PackList scanPacksImpl(final PackList old) {

540 final Map<String, PackFile> forReuse = reuseMap(old);

541 final long lastRead = System.currentTimeMillis();

542 final long lastModified = packDirectory.lastModified();

543 final Set<String> names = listPackDirectory();

544 final List<PackFile> list = new ArrayList<PackFile>(names.size() >> 2);

545 boolean foundNew = false;

546 for (final String indexName : names) {

547 // Must match "pack-[0-9a-f]{40}.idx" to be an index.

548 //

549 if (indexName.length() != 49 || !indexName.endsWith(".idx"))

550 continue;

551

552 final String base = indexName.substring(0, indexName.length() - 4);

553 final String packName = base + ".pack";

554 if (!names.contains(packName)) {

555 // Sometimes C Git's HTTP fetch transport leaves a

556 // .idx file behind and does not download the .pack.

557 // We have to skip over such useless indexes.

558 //

559 continue;

560 }

561

562 final PackFile oldPack = forReuse.remove(packName);

563 if (oldPack != null) {

564 list.add(oldPack);

565 continue;

566 }

567

568 final File packFile = new File(packDirectory, packName);

569 final File idxFile = new File(packDirectory, indexName);

570 list.add(new PackFile(idxFile, packFile));

571 foundNew = true;

572 }

573

574 // If we did not discover any new files, the modification time was not

575 // changed, and we did not remove any files, then the set of files is

576 // the same as the set we were given. Instead of building a new object

577 // return the same collection.

578 //

579 if (!foundNew && lastModified == old.lastModified && forReuse.isEmpty())

580 return old.updateLastRead(lastRead);

581

582 for (final PackFile p : forReuse.values()) {

583 p.close();

584 }

585

586 if (list.isEmpty())

587 return new PackList(lastRead, lastModified, NO_PACKS.packs);

588

589 final PackFile[] r = list.toArray(new PackFile[list.size()]);

590 Arrays.sort(r, PackFile.SORT);

591 return new PackList(lastRead, lastModified, r);

592 }

593

594 private static Map<String, PackFile> reuseMap(final PackList old) {

595 final Map<String, PackFile> forReuse = new HashMap<String, PackFile>();

596 for (final PackFile p : old.packs) {

597 if (p.invalid()) {

598 // The pack instance is corrupted, and cannot be safely used

599 // again. Do not include it in our reuse map.

600 //

601 p.close();

602 continue;

603 }

604

605 final PackFile prior = forReuse.put(p.getPackFile().getName(), p);

606 if (prior != null) {

607 // This should never occur. It should be impossible for us

608 // to have two pack files with the same name, as all of them

609 // came out of the same directory. If it does, we promised to

610 // close any PackFiles we did not reuse, so close the second,

611 // readers are likely to be actively using the first.

612 //

613 forReuse.put(prior.getPackFile().getName(), prior);

614 p.close();

615 }

616 }

617 return forReuse;

618 }

619

620 private Set<String> listPackDirectory() {

621 final String[] nameList = packDirectory.list();

622 if (nameList == null)

623 return Collections.emptySet();

624 final Set<String> nameSet = new HashSet<String>(nameList.length << 1);

625 for (final String name : nameList) {

626 if (name.startsWith("pack-"))

627 nameSet.add(name);

628 }

629 return nameSet;

630 }

631

632 AlternateHandle[] myAlternates() {

633 AlternateHandle[] alt = alternates.get();

634 if (alt == null) {

635 synchronized (alternates) {

636 alt = alternates.get();

637 if (alt == null) {

638 try {

639 alt = loadAlternates();

640 } catch (IOException e) {

641 alt = new AlternateHandle[0];

642 }

643 alternates.set(alt);

644 }

645 }

646 }

647 return alt;

648 }

649

650 private AlternateHandle[] loadAlternates() throws IOException {

651 final List<AlternateHandle> l = new ArrayList<AlternateHandle>(4);

652 final BufferedReader br = open(alternatesFile);

653 try {

654 String line;

655 while ((line = br.readLine()) != null) {

656 l.add(openAlternate(line));

657 }

658 } finally {

659 br.close();

660 }

661 return l.toArray(new AlternateHandle[l.size()]);

662 }

663

664 private static BufferedReader open(final File f)

665 throws FileNotFoundException {

666 return new BufferedReader(new FileReader(f));

667 }

668

669 private AlternateHandle openAlternate(final String location)

670 throws IOException {

671 final File objdir = fs.resolve(objects, location);

672 return openAlternate(objdir);

673 }

674

675 private AlternateHandle openAlternate(File objdir) throws IOException {

676 final File parent = objdir.getParentFile();

677 if (FileKey.isGitRepository(parent, fs)) {

678 FileKey key = FileKey.exact(parent, fs);

679 FileRepository db = (FileRepository) RepositoryCache.open(key);

680 return new AlternateRepository(db);

681 }

682

683 ObjectDirectory db = new ObjectDirectory(config, objdir, null, fs);

684 return new AlternateHandle(db);

685 }

686

687 private static final class PackList {

688 /** Last wall-clock time the directory was read. */

689 volatile long lastRead;

690

691 /** Last modification time of {@link ObjectDirectory#packDirectory}. */

692 final long lastModified;

693

694 /** All known packs, sorted by {@link PackFile#SORT}. */

695 final PackFile[] packs;

696

697 private boolean cannotBeRacilyClean;

698

699 PackList(final long lastRead, final long lastModified,

700 final PackFile[] packs) {

701 this.lastRead = lastRead;

702 this.lastModified = lastModified;

703 this.packs = packs;

704 this.cannotBeRacilyClean = notRacyClean(lastRead);

705 }

706

707 private boolean notRacyClean(final long read) {

708 return read - lastModified > 2 * 60 * 1000L;

709 }

710

711 PackList updateLastRead(final long now) {

712 if (notRacyClean(now))

713 cannotBeRacilyClean = true;

714 lastRead = now;

715 return this;

716 }

717

718 boolean tryAgain(final long currLastModified) {

719 // Any difference indicates the directory was modified.

720 //

721 if (lastModified != currLastModified)

722 return true;

723

724 // We have already determined the last read was far enough

725 // after the last modification that any new modifications

726 // are certain to change the last modified time.

727 //

728 if (cannotBeRacilyClean)

729 return false;

730

731 if (notRacyClean(lastRead)) {

732 // Our last read should have marked cannotBeRacilyClean,

733 // but this thread may not have seen the change. The read

734 // of the volatile field lastRead should have fixed that.

735 //

736 return false;

737 }

738

739 // We last read this directory too close to its last observed

740 // modification time. We may have missed a modification. Scan

741 // the directory again, to ensure we still see the same state.

742 //

743 return true;

744 }

745 }

746

747 @Override

748 public ObjectDatabase newCachedDatabase() {

749 return newCachedFileObjectDatabase();

750 }

751

752 FileObjectDatabase newCachedFileObjectDatabase() {

753 return new CachedObjectDirectory(this);

754 }

755 }