FileEntry.cc 18 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611
  1. /* <!-- copyright */
  2. /*
  3. * aria2 - The high speed download utility
  4. *
  5. * Copyright (C) 2006 Tatsuhiro Tsujikawa
  6. *
  7. * This program is free software; you can redistribute it and/or modify
  8. * it under the terms of the GNU General Public License as published by
  9. * the Free Software Foundation; either version 2 of the License, or
  10. * (at your option) any later version.
  11. *
  12. * This program is distributed in the hope that it will be useful,
  13. * but WITHOUT ANY WARRANTY; without even the implied warranty of
  14. * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
  15. * GNU General Public License for more details.
  16. *
  17. * You should have received a copy of the GNU General Public License
  18. * along with this program; if not, write to the Free Software
  19. * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
  20. *
  21. * In addition, as a special exception, the copyright holders give
  22. * permission to link the code of portions of this program with the
  23. * OpenSSL library under certain conditions as described in each
  24. * individual source file, and distribute linked combinations
  25. * including the two.
  26. * You must obey the GNU General Public License in all respects
  27. * for all of the code used other than OpenSSL. If you modify
  28. * file(s) with this exception, you may extend this exception to your
  29. * version of the file(s), but you are not obligated to do so. If you
  30. * do not wish to do so, delete this exception statement from your
  31. * version. If you delete this exception statement from all source
  32. * files in the program, then also delete it here.
  33. */
  34. /* copyright --> */
  35. #include "FileEntry.h"
  36. #include <cassert>
  37. #include <algorithm>
  38. #include "util.h"
  39. #include "URISelector.h"
  40. #include "Logger.h"
  41. #include "LogFactory.h"
  42. #include "wallclock.h"
  43. #include "a2algo.h"
  44. #include "uri.h"
  45. #include "PeerStat.h"
  46. #include "fmt.h"
  47. #include "ServerStatMan.h"
  48. #include "ServerStat.h"
  49. namespace aria2 {
  50. bool FileEntry::RequestFaster::operator()
  51. (const SharedHandle<Request>& lhs,
  52. const SharedHandle<Request>& rhs) const
  53. {
  54. if(!lhs->getPeerStat()) {
  55. return false;
  56. }
  57. if(!rhs->getPeerStat()) {
  58. return true;
  59. }
  60. int lspd = lhs->getPeerStat()->getAvgDownloadSpeed();
  61. int rspd = rhs->getPeerStat()->getAvgDownloadSpeed();
  62. return lspd > rspd || (lspd == rspd && lhs.get() < rhs.get());
  63. }
  64. FileEntry::FileEntry
  65. (const std::string& path,
  66. int64_t length,
  67. int64_t offset,
  68. const std::vector<std::string>& uris)
  69. : path_(path),
  70. uris_(uris.begin(), uris.end()),
  71. length_(length),
  72. offset_(offset),
  73. requested_(true),
  74. uniqueProtocol_(false),
  75. maxConnectionPerServer_(1),
  76. lastFasterReplace_(0)
  77. {}
  78. FileEntry::FileEntry()
  79. : length_(0),
  80. offset_(0),
  81. requested_(false),
  82. uniqueProtocol_(false),
  83. maxConnectionPerServer_(1)
  84. {}
  85. FileEntry::~FileEntry() {}
  86. FileEntry& FileEntry::operator=(const FileEntry& entry)
  87. {
  88. if(this != &entry) {
  89. path_ = entry.path_;
  90. length_ = entry.length_;
  91. offset_ = entry.offset_;
  92. requested_ = entry.requested_;
  93. }
  94. return *this;
  95. }
  96. bool FileEntry::operator<(const FileEntry& fileEntry) const
  97. {
  98. return offset_ < fileEntry.offset_;
  99. }
  100. bool FileEntry::exists() const
  101. {
  102. return File(getPath()).exists();
  103. }
  104. int64_t FileEntry::gtoloff(int64_t goff) const
  105. {
  106. assert(offset_ <= goff);
  107. return goff-offset_;
  108. }
  109. void FileEntry::getUris(std::vector<std::string>& uris) const
  110. {
  111. uris.insert(uris.end(), spentUris_.begin(), spentUris_.end());
  112. uris.insert(uris.end(), uris_.begin(), uris_.end());
  113. }
  114. namespace {
  115. template<typename InputIterator, typename OutputIterator>
  116. OutputIterator enumerateInFlightHosts
  117. (InputIterator first, InputIterator last, OutputIterator out)
  118. {
  119. for(; first != last; ++first) {
  120. uri_split_result us;
  121. if(uri_split(&us, (*first)->getUri().c_str()) == 0) {
  122. *out++ = uri::getFieldString(us, USR_HOST, (*first)->getUri().c_str());
  123. }
  124. }
  125. return out;
  126. }
  127. } // namespace
  128. SharedHandle<Request>
  129. FileEntry::getRequest
  130. (const SharedHandle<URISelector>& selector,
  131. bool uriReuse,
  132. const std::vector<std::pair<size_t, std::string> >& usedHosts,
  133. const std::string& referer,
  134. const std::string& method)
  135. {
  136. SharedHandle<Request> req;
  137. if(requestPool_.empty()) {
  138. std::vector<std::string> inFlightHosts;
  139. enumerateInFlightHosts(inFlightRequests_.begin(), inFlightRequests_.end(),
  140. std::back_inserter(inFlightHosts));
  141. for(int g = 0; g < 2; ++g) {
  142. std::vector<std::string> pending;
  143. std::vector<std::string> ignoreHost;
  144. while(1) {
  145. std::string uri = selector->select(this, usedHosts);
  146. if(uri.empty()) {
  147. break;
  148. }
  149. req.reset(new Request());
  150. if(req->setUri(uri)) {
  151. if(std::count(inFlightHosts.begin(),
  152. inFlightHosts.end(),req->getHost())
  153. >= maxConnectionPerServer_) {
  154. pending.push_back(uri);
  155. ignoreHost.push_back(req->getHost());
  156. req.reset();
  157. continue;
  158. }
  159. if(referer == "*") {
  160. // Assuming uri has already been percent-encoded.
  161. req->setReferer(uri);
  162. } else {
  163. req->setReferer(util::percentEncodeMini(referer));
  164. }
  165. req->setMethod(method);
  166. spentUris_.push_back(uri);
  167. inFlightRequests_.insert(req);
  168. break;
  169. } else {
  170. req.reset();
  171. }
  172. }
  173. uris_.insert(uris_.begin(), pending.begin(), pending.end());
  174. if(g == 0 && uriReuse && !req && uris_.size() == pending.size()) {
  175. // Reuse URIs other than ones in pending
  176. reuseUri(ignoreHost);
  177. } else {
  178. break;
  179. }
  180. }
  181. } else {
  182. // Skip Request object if it is still
  183. // sleeping(Request::getWakeTime() < global::wallclock()). If all
  184. // pooled objects are sleeping, return first one. Caller should
  185. // inspect returned object's getWakeTime().
  186. RequestPool::iterator i = requestPool_.begin();
  187. RequestPool::iterator eoi = requestPool_.end();
  188. for(; i != eoi; ++i) {
  189. if((*i)->getWakeTime() <= global::wallclock()) {
  190. break;
  191. }
  192. }
  193. if(i == eoi) {
  194. i = requestPool_.begin();
  195. }
  196. req = *i;
  197. requestPool_.erase(i);
  198. inFlightRequests_.insert(req);
  199. A2_LOG_DEBUG(fmt("Picked up from pool: %s", req->getUri().c_str()));
  200. }
  201. return req;
  202. }
  203. SharedHandle<Request>
  204. FileEntry::findFasterRequest(const SharedHandle<Request>& base)
  205. {
  206. const int startupIdleTime = 10;
  207. if(requestPool_.empty() ||
  208. lastFasterReplace_.difference(global::wallclock()) < startupIdleTime) {
  209. return SharedHandle<Request>();
  210. }
  211. const SharedHandle<PeerStat>& fastest =
  212. (*requestPool_.begin())->getPeerStat();
  213. if(!fastest) {
  214. return SharedHandle<Request>();
  215. }
  216. const SharedHandle<PeerStat>& basestat = base->getPeerStat();
  217. // TODO hard coded value. See PREF_STARTUP_IDLE_TIME
  218. if(!basestat ||
  219. (basestat->getDownloadStartTime().
  220. difference(global::wallclock()) >= startupIdleTime &&
  221. fastest->getAvgDownloadSpeed()*0.8 > basestat->calculateDownloadSpeed())){
  222. // TODO we should consider that "fastest" is very slow.
  223. SharedHandle<Request> fastestRequest = *requestPool_.begin();
  224. requestPool_.erase(requestPool_.begin());
  225. inFlightRequests_.insert(fastestRequest);
  226. lastFasterReplace_ = global::wallclock();
  227. return fastestRequest;
  228. }
  229. return SharedHandle<Request>();
  230. }
  231. SharedHandle<Request>
  232. FileEntry::findFasterRequest
  233. (const SharedHandle<Request>& base,
  234. const std::vector<std::pair<size_t, std::string> >& usedHosts,
  235. const SharedHandle<ServerStatMan>& serverStatMan)
  236. {
  237. const int startupIdleTime = 10;
  238. const int SPEED_THRESHOLD = 20*1024;
  239. if(lastFasterReplace_.difference(global::wallclock()) < startupIdleTime) {
  240. return SharedHandle<Request>();
  241. }
  242. std::vector<std::string> inFlightHosts;
  243. enumerateInFlightHosts(inFlightRequests_.begin(), inFlightRequests_.end(),
  244. std::back_inserter(inFlightHosts));
  245. const SharedHandle<PeerStat>& basestat = base->getPeerStat();
  246. A2_LOG_DEBUG("Search faster server using ServerStat.");
  247. // Use first 10 good URIs to introduce some randomness.
  248. const size_t NUM_URI = 10;
  249. std::vector<std::pair<SharedHandle<ServerStat>, std::string> > fastCands;
  250. std::vector<std::string> normCands;
  251. for(std::deque<std::string>::const_iterator i = uris_.begin(),
  252. eoi = uris_.end(); i != eoi && fastCands.size() < NUM_URI; ++i) {
  253. uri_split_result us;
  254. if(uri_split(&us, (*i).c_str()) == -1) {
  255. continue;
  256. }
  257. std::string host = uri::getFieldString(us, USR_HOST, (*i).c_str());
  258. std::string protocol = uri::getFieldString(us, USR_SCHEME, (*i).c_str());
  259. if(std::count(inFlightHosts.begin(), inFlightHosts.end(), host)
  260. >= maxConnectionPerServer_) {
  261. A2_LOG_DEBUG(fmt("%s has already used %d times, not considered.",
  262. (*i).c_str(),
  263. maxConnectionPerServer_));
  264. continue;
  265. }
  266. if(findSecond(usedHosts.begin(), usedHosts.end(), host) !=
  267. usedHosts.end()) {
  268. A2_LOG_DEBUG(fmt("%s is in usedHosts, not considered", (*i).c_str()));
  269. continue;
  270. }
  271. SharedHandle<ServerStat> ss = serverStatMan->find(host, protocol);
  272. if(ss && ss->isOK()) {
  273. if((basestat &&
  274. ss->getDownloadSpeed() > basestat->calculateDownloadSpeed()*1.5) ||
  275. (!basestat && ss->getDownloadSpeed() > SPEED_THRESHOLD)) {
  276. fastCands.push_back(std::make_pair(ss, *i));
  277. }
  278. }
  279. }
  280. if(!fastCands.empty()) {
  281. std::sort(fastCands.begin(), fastCands.end(), ServerStatFaster());
  282. SharedHandle<Request> fastestRequest(new Request());
  283. const std::string& uri = fastCands.front().second;
  284. A2_LOG_DEBUG(fmt("Selected %s from fastCands", uri.c_str()));
  285. fastestRequest->setUri(uri);
  286. fastestRequest->setReferer(base->getReferer());
  287. uris_.erase(std::find(uris_.begin(), uris_.end(), uri));
  288. spentUris_.push_back(uri);
  289. inFlightRequests_.insert(fastestRequest);
  290. lastFasterReplace_ = global::wallclock();
  291. return fastestRequest;
  292. }
  293. A2_LOG_DEBUG("No faster server found.");
  294. return SharedHandle<Request>();
  295. }
  296. void FileEntry::storePool(const SharedHandle<Request>& request)
  297. {
  298. const SharedHandle<PeerStat>& peerStat = request->getPeerStat();
  299. if(peerStat) {
  300. // We need to calculate average download speed here in order to
  301. // store Request in the right position in the pool.
  302. peerStat->calculateAvgDownloadSpeed();
  303. }
  304. requestPool_.insert(request);
  305. }
  306. void FileEntry::poolRequest(const SharedHandle<Request>& request)
  307. {
  308. removeRequest(request);
  309. if(!request->removalRequested()) {
  310. storePool(request);
  311. }
  312. }
  313. bool FileEntry::removeRequest(const SharedHandle<Request>& request)
  314. {
  315. return inFlightRequests_.erase(request) == 1;
  316. }
  317. void FileEntry::removeURIWhoseHostnameIs(const std::string& hostname)
  318. {
  319. std::deque<std::string> newURIs;
  320. for(std::deque<std::string>::const_iterator itr = uris_.begin(),
  321. eoi = uris_.end(); itr != eoi; ++itr) {
  322. uri_split_result us;
  323. if(uri_split(&us, (*itr).c_str()) == -1) {
  324. continue;
  325. }
  326. if(us.fields[USR_HOST].len != hostname.size() ||
  327. memcmp((*itr).c_str()+us.fields[USR_HOST].off, hostname.c_str(),
  328. hostname.size()) != 0) {
  329. newURIs.push_back(*itr);
  330. }
  331. }
  332. A2_LOG_DEBUG(fmt("Removed %lu duplicate hostname URIs for path=%s",
  333. static_cast<unsigned long>(uris_.size()-newURIs.size()),
  334. getPath().c_str()));
  335. uris_.swap(newURIs);
  336. }
  337. void FileEntry::removeIdenticalURI(const std::string& uri)
  338. {
  339. uris_.erase(std::remove(uris_.begin(), uris_.end(), uri), uris_.end());
  340. }
  341. void FileEntry::addURIResult(std::string uri, error_code::Value result)
  342. {
  343. uriResults_.push_back(URIResult(uri, result));
  344. }
  345. namespace {
  346. class FindURIResultByResult {
  347. private:
  348. error_code::Value r_;
  349. public:
  350. FindURIResultByResult(error_code::Value r):r_(r) {}
  351. bool operator()(const URIResult& uriResult) const
  352. {
  353. return uriResult.getResult() == r_;
  354. }
  355. };
  356. } // namespace
  357. void FileEntry::extractURIResult
  358. (std::deque<URIResult>& res, error_code::Value r)
  359. {
  360. std::deque<URIResult>::iterator i =
  361. std::stable_partition(uriResults_.begin(), uriResults_.end(),
  362. FindURIResultByResult(r));
  363. std::copy(uriResults_.begin(), i, std::back_inserter(res));
  364. uriResults_.erase(uriResults_.begin(), i);
  365. }
  366. void FileEntry::reuseUri(const std::vector<std::string>& ignore)
  367. {
  368. if(A2_LOG_DEBUG_ENABLED) {
  369. for(std::vector<std::string>::const_iterator i = ignore.begin(),
  370. eoi = ignore.end(); i != eoi; ++i) {
  371. A2_LOG_DEBUG(fmt("ignore host=%s", (*i).c_str()));
  372. }
  373. }
  374. std::deque<std::string> uris = spentUris_;
  375. std::sort(uris.begin(), uris.end());
  376. uris.erase(std::unique(uris.begin(), uris.end()), uris.end());
  377. std::vector<std::string> errorUris(uriResults_.size());
  378. std::transform(uriResults_.begin(), uriResults_.end(),
  379. errorUris.begin(), std::mem_fun_ref(&URIResult::getURI));
  380. std::sort(errorUris.begin(), errorUris.end());
  381. errorUris.erase(std::unique(errorUris.begin(), errorUris.end()),
  382. errorUris.end());
  383. if(A2_LOG_DEBUG_ENABLED) {
  384. for(std::vector<std::string>::const_iterator i = errorUris.begin(),
  385. eoi = errorUris.end(); i != eoi; ++i) {
  386. A2_LOG_DEBUG(fmt("error URI=%s", (*i).c_str()));
  387. }
  388. }
  389. std::vector<std::string> reusableURIs;
  390. std::set_difference(uris.begin(), uris.end(),
  391. errorUris.begin(), errorUris.end(),
  392. std::back_inserter(reusableURIs));
  393. std::vector<std::string>::iterator insertionPoint = reusableURIs.begin();
  394. for(std::vector<std::string>::iterator i = reusableURIs.begin(),
  395. eoi = reusableURIs.end(); i != eoi; ++i) {
  396. uri_split_result us;
  397. if(uri_split(&us, (*i).c_str()) == 0 &&
  398. std::find(ignore.begin(), ignore.end(),
  399. uri::getFieldString(us, USR_HOST, (*i).c_str()))
  400. == ignore.end()) {
  401. if(i != insertionPoint) {
  402. *insertionPoint = *i;
  403. }
  404. ++insertionPoint;
  405. }
  406. }
  407. reusableURIs.erase(insertionPoint, reusableURIs.end());
  408. size_t ininum = reusableURIs.size();
  409. if(A2_LOG_DEBUG_ENABLED) {
  410. A2_LOG_DEBUG(fmt("Found %u reusable URIs",
  411. static_cast<unsigned int>(ininum)));
  412. for(std::vector<std::string>::const_iterator i = reusableURIs.begin(),
  413. eoi = reusableURIs.end(); i != eoi; ++i) {
  414. A2_LOG_DEBUG(fmt("URI=%s", (*i).c_str()));
  415. }
  416. }
  417. uris_.insert(uris_.end(), reusableURIs.begin(), reusableURIs.end());
  418. }
  419. void FileEntry::releaseRuntimeResource()
  420. {
  421. requestPool_.clear();
  422. inFlightRequests_.clear();
  423. }
  424. namespace {
  425. template<typename InputIterator>
  426. void putBackUri
  427. (std::deque<std::string>& uris,
  428. InputIterator first,
  429. InputIterator last)
  430. {
  431. for(; first != last; ++first) {
  432. uris.push_front((*first)->getUri());
  433. }
  434. }
  435. } // namespace
  436. void FileEntry::putBackRequest()
  437. {
  438. putBackUri(uris_, requestPool_.begin(), requestPool_.end());
  439. putBackUri(uris_, inFlightRequests_.begin(), inFlightRequests_.end());
  440. }
  441. namespace {
  442. template<typename InputIterator, typename T>
  443. InputIterator findRequestByUri
  444. (InputIterator first, InputIterator last, const T& uri)
  445. {
  446. for(; first != last; ++first) {
  447. if(!(*first)->removalRequested() && (*first)->getUri() == uri) {
  448. return first;
  449. }
  450. }
  451. return last;
  452. }
  453. } // namespace
  454. bool FileEntry::removeUri(const std::string& uri)
  455. {
  456. std::deque<std::string>::iterator itr =
  457. std::find(spentUris_.begin(), spentUris_.end(), uri);
  458. if(itr == spentUris_.end()) {
  459. itr = std::find(uris_.begin(), uris_.end(), uri);
  460. if(itr == uris_.end()) {
  461. return false;
  462. } else {
  463. uris_.erase(itr);
  464. return true;
  465. }
  466. } else {
  467. spentUris_.erase(itr);
  468. SharedHandle<Request> req;
  469. InFlightRequestSet::iterator riter =
  470. findRequestByUri(inFlightRequests_.begin(), inFlightRequests_.end(), uri);
  471. if(riter == inFlightRequests_.end()) {
  472. RequestPool::iterator riter = findRequestByUri(requestPool_.begin(),
  473. requestPool_.end(), uri);
  474. if(riter == requestPool_.end()) {
  475. return true;
  476. } else {
  477. req = *riter;
  478. requestPool_.erase(riter);
  479. }
  480. } else {
  481. req = *riter;
  482. }
  483. req->requestRemoval();
  484. return true;
  485. }
  486. }
  487. std::string FileEntry::getBasename() const
  488. {
  489. return File(path_).getBasename();
  490. }
  491. std::string FileEntry::getDirname() const
  492. {
  493. return File(path_).getDirname();
  494. }
  495. size_t FileEntry::setUris(const std::vector<std::string>& uris)
  496. {
  497. uris_.clear();
  498. return addUris(uris.begin(), uris.end());
  499. }
  500. bool FileEntry::addUri(const std::string& uri)
  501. {
  502. std::string peUri = util::percentEncodeMini(uri);
  503. if(uri_split(NULL, peUri.c_str()) == 0) {
  504. uris_.push_back(peUri);
  505. return true;
  506. } else {
  507. return false;
  508. }
  509. }
  510. bool FileEntry::insertUri(const std::string& uri, size_t pos)
  511. {
  512. std::string peUri = util::percentEncodeMini(uri);
  513. if(uri_split(NULL, peUri.c_str()) == 0) {
  514. pos = std::min(pos, uris_.size());
  515. uris_.insert(uris_.begin()+pos, peUri);
  516. return true;
  517. } else {
  518. return false;
  519. }
  520. }
  521. void FileEntry::setPath(const std::string& path)
  522. {
  523. path_ = path;
  524. }
  525. void FileEntry::setContentType(const std::string& contentType)
  526. {
  527. contentType_ = contentType;
  528. }
  529. size_t FileEntry::countInFlightRequest() const
  530. {
  531. return inFlightRequests_.size();
  532. }
  533. size_t FileEntry::countPooledRequest() const
  534. {
  535. return requestPool_.size();
  536. }
  537. void FileEntry::setOriginalName(const std::string& originalName)
  538. {
  539. originalName_ = originalName;
  540. }
  541. bool FileEntry::emptyRequestUri() const
  542. {
  543. return uris_.empty() && inFlightRequests_.empty() && requestPool_.empty();
  544. }
  545. void writeFilePath
  546. (std::ostream& o,
  547. const SharedHandle<FileEntry>& entry,
  548. bool memory)
  549. {
  550. if(entry->getPath().empty()) {
  551. std::vector<std::string> uris;
  552. entry->getUris(uris);
  553. if(uris.empty()) {
  554. o << "n/a";
  555. } else {
  556. o << uris.front();
  557. }
  558. } else {
  559. if(memory) {
  560. o << "[MEMORY]" << File(entry->getPath()).getBasename();
  561. } else {
  562. o << entry->getPath();
  563. }
  564. }
  565. }
  566. } // namespace aria2