626 lines · cpp
1// RUN: %clangxx_tsan %s -o %t -DLockType=PthreadMutex2// RUN: %deflake %run %t | FileCheck %s --check-prefix=CHECK --check-prefix=CHECK-NOT-SECOND3// RUN: %env_tsan_opts=second_deadlock_stack=1 %deflake %run %t | FileCheck %s --check-prefix=CHECK --check-prefix=CHECK-SECOND4// RUN: %clangxx_tsan %s -o %t -DLockType=PthreadSpinLock5// RUN: %deflake %run %t | FileCheck %s6// RUN: %clangxx_tsan %s -o %t -DLockType=PthreadRWLock7// RUN: %deflake %run %t | FileCheck %s --check-prefix=CHECK --check-prefix=CHECK-RD8// RUN: %clangxx_tsan %s -o %t -DLockType=PthreadRecursiveMutex9// RUN: %deflake %run %t | FileCheck %s --check-prefix=CHECK --check-prefix=CHECK-REC10#include "test.h"11#undef NDEBUG12#include <assert.h>13#include <new>14 15#ifndef LockType16#define LockType PthreadMutex17#endif18 19// You can optionally pass [test_number [iter_count]] on command line.20static int test_number = -1;21static int iter_count = 100000;22 23class PthreadMutex {24 public:25 explicit PthreadMutex(bool recursive = false) {26 if (recursive) {27 pthread_mutexattr_t attr;28 pthread_mutexattr_init(&attr);29 pthread_mutexattr_settype(&attr, PTHREAD_MUTEX_RECURSIVE);30 assert(0 == pthread_mutex_init(&mu_, &attr));31 } else {32 assert(0 == pthread_mutex_init(&mu_, 0));33 }34 }35 ~PthreadMutex() {36 assert(0 == pthread_mutex_destroy(&mu_));37 (void)padding_;38 }39 static bool supports_read_lock() { return false; }40 static bool supports_recursive_lock() { return false; }41 void lock() { assert(0 == pthread_mutex_lock(&mu_)); }42 void unlock() { assert(0 == pthread_mutex_unlock(&mu_)); }43 bool try_lock() { return 0 == pthread_mutex_trylock(&mu_); }44 void rdlock() { assert(0); }45 void rdunlock() { assert(0); }46 bool try_rdlock() { assert(0); }47 48 private:49 pthread_mutex_t mu_;50 char padding_[64 - sizeof(pthread_mutex_t)];51};52 53class PthreadRecursiveMutex : public PthreadMutex {54 public:55 PthreadRecursiveMutex() : PthreadMutex(true) { }56 static bool supports_recursive_lock() { return true; }57};58 59#ifndef __APPLE__60class PthreadSpinLock {61 public:62 PthreadSpinLock() { assert(0 == pthread_spin_init(&mu_, 0)); }63 ~PthreadSpinLock() {64 assert(0 == pthread_spin_destroy(&mu_));65 (void)padding_;66 }67 static bool supports_read_lock() { return false; }68 static bool supports_recursive_lock() { return false; }69 void lock() { assert(0 == pthread_spin_lock(&mu_)); }70 void unlock() { assert(0 == pthread_spin_unlock(&mu_)); }71 bool try_lock() { return 0 == pthread_spin_trylock(&mu_); }72 void rdlock() { assert(0); }73 void rdunlock() { assert(0); }74 bool try_rdlock() { assert(0); }75 76 private:77 pthread_spinlock_t mu_;78 char padding_[64 - sizeof(pthread_spinlock_t)];79};80#else81class PthreadSpinLock : public PthreadMutex { };82#endif83 84class PthreadRWLock {85 public:86 PthreadRWLock() { assert(0 == pthread_rwlock_init(&mu_, 0)); }87 ~PthreadRWLock() {88 assert(0 == pthread_rwlock_destroy(&mu_));89 (void)padding_;90 }91 static bool supports_read_lock() { return true; }92 static bool supports_recursive_lock() { return false; }93 void lock() { assert(0 == pthread_rwlock_wrlock(&mu_)); }94 void unlock() { assert(0 == pthread_rwlock_unlock(&mu_)); }95 bool try_lock() { return 0 == pthread_rwlock_trywrlock(&mu_); }96 void rdlock() { assert(0 == pthread_rwlock_rdlock(&mu_)); }97 void rdunlock() { assert(0 == pthread_rwlock_unlock(&mu_)); }98 bool try_rdlock() { return 0 == pthread_rwlock_tryrdlock(&mu_); }99 100 private:101 pthread_rwlock_t mu_;102 char padding_[256 - sizeof(pthread_rwlock_t)];103};104 105class LockTest {106 public:107 LockTest() : n_(), locks_() {}108 void Init(size_t n) {109 n_ = n;110 locks_ = new LockType*[n_];111 for (size_t i = 0; i < n_; i++)112 locks_[i] = new LockType;113 }114 ~LockTest() {115 for (size_t i = 0; i < n_; i++)116 delete locks_[i];117 delete [] locks_;118 }119 void L(size_t i) {120 assert(i < n_);121 locks_[i]->lock();122 }123 124 void U(size_t i) {125 assert(i < n_);126 locks_[i]->unlock();127 }128 129 void RL(size_t i) {130 assert(i < n_);131 locks_[i]->rdlock();132 }133 134 void RU(size_t i) {135 assert(i < n_);136 locks_[i]->rdunlock();137 }138 139 void *A(size_t i) {140 assert(i < n_);141 return locks_[i];142 }143 144 bool T(size_t i) {145 assert(i < n_);146 return locks_[i]->try_lock();147 }148 149 // Simple lock order onversion.150 void Test1() {151 if (test_number > 0 && test_number != 1) return;152 fprintf(stderr, "Starting Test1\n");153 // CHECK: Starting Test1154 Init(5);155 print_address("Expecting lock inversion: ", 2, A(0), A(1));156 // CHECK: Expecting lock inversion: [[A1:0x[a-f0-9]*]] [[A2:0x[a-f0-9]*]]157 Lock_0_1();158 Lock_1_0();159 // CHECK: WARNING: ThreadSanitizer: lock-order-inversion (potential deadlock)160 // CHECK: Cycle in lock order graph: [[M1:M[0-9]+]] ([[A1]]) => [[M2:M[0-9]+]] ([[A2]]) => [[M1]]161 // CHECK: Mutex [[M2]] acquired here while holding mutex [[M1]]162 // CHECK: #0 pthread_163 // CHECK-SECOND: Mutex [[M1]] previously acquired by the same thread here:164 // CHECK-SECOND: #0 pthread_165 // CHECK-NOT-SECOND: second_deadlock_stack=1 to get more informative warning message166 // CHECK-NOT-SECOND-NOT: #0 pthread_167 // CHECK: Mutex [[M1]] acquired here while holding mutex [[M2]]168 // CHECK: #0 pthread_169 // CHECK-SECOND: Mutex [[M2]] previously acquired by the same thread here:170 // CHECK-SECOND: #0 pthread_171 // CHECK-NOT-SECOND-NOT: #0 pthread_172 // CHECK-NOT: WARNING: ThreadSanitizer:173 }174 175 // Simple lock order inversion with 3 locks.176 void Test2() {177 if (test_number > 0 && test_number != 2) return;178 fprintf(stderr, "Starting Test2\n");179 // CHECK: Starting Test2180 Init(5);181 print_address("Expecting lock inversion: ", 3, A(0), A(1), A(2));182 // CHECK: Expecting lock inversion: [[A1:0x[a-f0-9]*]] [[A2:0x[a-f0-9]*]] [[A3:0x[a-f0-9]*]]183 Lock2(0, 1);184 Lock2(1, 2);185 Lock2(2, 0);186 // CHECK: WARNING: ThreadSanitizer: lock-order-inversion (potential deadlock)187 // CHECK: Cycle in lock order graph: [[M1:M[0-9]+]] ([[A1]]) => [[M2:M[0-9]+]] ([[A2]]) => [[M3:M[0-9]+]] ([[A3]]) => [[M1]]188 // CHECK-NOT: WARNING: ThreadSanitizer:189 }190 191 // Lock order inversion with lots of new locks created (but not used)192 // between. Since the new locks are not used we should still detect the193 // deadlock.194 void Test3() {195 if (test_number > 0 && test_number != 3) return;196 fprintf(stderr, "Starting Test3\n");197 // CHECK: Starting Test3198 Init(5);199 Lock_0_1();200 L(2);201 CreateAndDestroyManyLocks();202 U(2);203 Lock_1_0();204 // CHECK: WARNING: ThreadSanitizer: lock-order-inversion (potential deadlock)205 // CHECK-NOT: WARNING: ThreadSanitizer:206 }207 208 // lock l0=>l1; then create and use lots of locks; then lock l1=>l0.209 // The deadlock epoch should have changed and we should not report anything.210 void Test4() {211 if (test_number > 0 && test_number != 4) return;212 fprintf(stderr, "Starting Test4\n");213 // CHECK: Starting Test4214 Init(5);215 Lock_0_1();216 L(2);217 CreateLockUnlockAndDestroyManyLocks();218 U(2);219 Lock_1_0();220 // CHECK-NOT: WARNING: ThreadSanitizer:221 }222 223 void Test5() {224 if (test_number > 0 && test_number != 5) return;225 fprintf(stderr, "Starting Test5\n");226 // CHECK: Starting Test5227 Init(5);228 RunThreads(&LockTest::Lock_0_1<true>, &LockTest::Lock_1_0<true>);229 // CHECK: WARNING: ThreadSanitizer: lock-order-inversion230 // CHECK: Cycle in lock order graph: [[M1:M[0-9]+]] ({{.*}}) => [[M2:M[0-9]+]] ({{.*}}) => [[M1]]231 // CHECK: Mutex [[M2]] acquired here while holding mutex [[M1]] in thread [[T1:T[0-9]+]]232 // CHECK: Mutex [[M1]] acquired here while holding mutex [[M2]] in thread [[T2:T[0-9]+]]233 // CHECK: Thread [[T1]] {{.*}} created by main thread234 // CHECK: Thread [[T2]] {{.*}} created by main thread235 // CHECK-NOT: WARNING: ThreadSanitizer:236 }237 238 void Test6() {239 if (test_number > 0 && test_number != 6) return;240 fprintf(stderr, "Starting Test6: 3 threads lock/unlock private mutexes\n");241 // CHECK: Starting Test6242 Init(100);243 // CHECK-NOT: WARNING: ThreadSanitizer:244 RunThreads(&LockTest::Lock1_Loop_0, &LockTest::Lock1_Loop_1,245 &LockTest::Lock1_Loop_2);246 }247 248 void Test7() {249 if (test_number > 0 && test_number != 7) return;250 fprintf(stderr, "Starting Test7\n");251 // CHECK: Starting Test7252 Init(10);253 L(0); T(1); U(1); U(0);254 T(1); L(0); U(1); U(0);255 // CHECK-NOT: WARNING: ThreadSanitizer:256 fprintf(stderr, "No cycle: 0=>1\n");257 // CHECK: No cycle: 0=>1258 259 T(2); L(3); U(3); U(2);260 L(3); T(2); U(3); U(2);261 // CHECK-NOT: WARNING: ThreadSanitizer:262 fprintf(stderr, "No cycle: 2=>3\n");263 // CHECK: No cycle: 2=>3264 265 T(4); L(5); U(4); U(5);266 L(5); L(4); U(4); U(5);267 // CHECK: WARNING: ThreadSanitizer: lock-order-inversion268 fprintf(stderr, "Have cycle: 4=>5\n");269 // CHECK: Have cycle: 4=>5270 271 L(7); L(6); U(6); U(7);272 T(6); L(7); U(6); U(7);273 // CHECK: WARNING: ThreadSanitizer: lock-order-inversion274 fprintf(stderr, "Have cycle: 6=>7\n");275 // CHECK: Have cycle: 6=>7276 }277 278 void Test8() {279 if (test_number > 0 && test_number != 8) return;280 if (!LockType::supports_read_lock()) return;281 fprintf(stderr, "Starting Test8\n");282 Init(5);283 // CHECK-RD: Starting Test8284 RL(0); L(1); RU(0); U(1);285 L(1); RL(0); RU(0); U(1);286 // CHECK-RD: WARNING: ThreadSanitizer: lock-order-inversion287 fprintf(stderr, "Have cycle: 0=>1\n");288 // CHECK-RD: Have cycle: 0=>1289 290 RL(2); RL(3); RU(2); RU(3);291 RL(3); RL(2); RU(2); RU(3);292 // CHECK-RD: WARNING: ThreadSanitizer: lock-order-inversion293 fprintf(stderr, "Have cycle: 2=>3\n");294 // CHECK-RD: Have cycle: 2=>3295 }296 297 void Test9() {298 if (test_number > 0 && test_number != 9) return;299 if (!LockType::supports_recursive_lock()) return;300 fprintf(stderr, "Starting Test9\n");301 // CHECK-REC: Starting Test9302 Init(5);303 L(0); L(0); L(0); L(1); U(1); U(0); U(0); U(0);304 L(1); L(1); L(1); L(0); U(0); U(1); U(1); U(1);305 // CHECK-REC: WARNING: ThreadSanitizer: lock-order-inversion306 }307 308 void Test10() {309 if (test_number > 0 && test_number != 10) return;310 fprintf(stderr, "Starting Test10: 4 threads lock/unlock 4 private mutexes, one under another\n");311 // CHECK: Starting Test10312 Init(100);313 // CHECK-NOT: WARNING: ThreadSanitizer:314 RunThreads(&LockTest::Test10_Thread1, &LockTest::Test10_Thread2,315 &LockTest::Test10_Thread3, &LockTest::Test10_Thread4);316 }317 void Test10_Thread1() { Test10_Thread(0); }318 void Test10_Thread2() { Test10_Thread(10); }319 void Test10_Thread3() { Test10_Thread(20); }320 void Test10_Thread4() { Test10_Thread(30); }321 void Test10_Thread(size_t m) {322 for (int i = 0; i < iter_count; i++) {323 L(m + 0);324 L(m + 1);325 L(m + 2);326 L(m + 3);327 U(m + 3);328 U(m + 2);329 U(m + 1);330 U(m + 0);331 }332 }333 334 void Test11() {335 if (test_number > 0 && test_number != 11) return;336 fprintf(stderr, "Starting Test11: 4 threads lock/unlock 4 private mutexes, all under another private mutex\n");337 // CHECK: Starting Test11338 Init(500);339 // CHECK-NOT: WARNING: ThreadSanitizer:340 RunThreads(&LockTest::Test11_Thread1, &LockTest::Test11_Thread2,341 &LockTest::Test11_Thread3, &LockTest::Test11_Thread4);342 }343 void Test11_Thread1() { Test10_Thread(0); }344 void Test11_Thread2() { Test10_Thread(10); }345 void Test11_Thread3() { Test10_Thread(20); }346 void Test11_Thread4() { Test10_Thread(30); }347 void Test11_Thread(size_t m) {348 for (int i = 0; i < iter_count; i++) {349 L(m);350 L(m + 100);351 U(m + 100);352 L(m + 200);353 U(m + 200);354 L(m + 300);355 U(m + 300);356 L(m + 400);357 U(m + 500);358 U(m);359 }360 }361 362 void Test12() {363 if (test_number > 0 && test_number != 12) return;364 if (!LockType::supports_read_lock()) return;365 fprintf(stderr, "Starting Test12: 4 threads read lock/unlock 4 shared mutexes, one under another\n");366 // CHECK-RD: Starting Test12367 Init(500);368 // CHECK-RD-NOT: WARNING: ThreadSanitizer:369 RunThreads(&LockTest::Test12_Thread, &LockTest::Test12_Thread,370 &LockTest::Test12_Thread, &LockTest::Test12_Thread);371 }372 void Test12_Thread() {373 for (int i = 0; i < iter_count; i++) {374 RL(000);375 RL(100);376 RL(200);377 RL(300);378 RU(300);379 RU(200);380 RU(100);381 RU(000);382 }383 }384 385 void Test13() {386 if (test_number > 0 && test_number != 13) return;387 if (!LockType::supports_read_lock()) return;388 fprintf(stderr, "Starting Test13: 4 threads read lock/unlock 4 shared mutexes, all under another shared mutex\n");389 // CHECK-RD: Starting Test13390 Init(500);391 // CHECK-RD-NOT: WARNING: ThreadSanitizer:392 RunThreads(&LockTest::Test13_Thread, &LockTest::Test13_Thread,393 &LockTest::Test13_Thread, &LockTest::Test13_Thread);394 }395 void Test13_Thread() {396 for (int i = 0; i < iter_count; i++) {397 RL(0);398 RL(100);399 RU(100);400 RL(200);401 RU(200);402 RL(300);403 RU(300);404 RL(400);405 RU(400);406 RU(0);407 }408 }409 410 void Test14() {411 if (test_number > 0 && test_number != 14) return;412 fprintf(stderr, "Starting Test14: create lots of locks in 4 threads\n");413 Init(10);414 // CHECK-RD: Starting Test14415 RunThreads(&LockTest::CreateAndDestroyLocksLoop,416 &LockTest::CreateAndDestroyLocksLoop,417 &LockTest::CreateAndDestroyLocksLoop,418 &LockTest::CreateAndDestroyLocksLoop);419 }420 421 void Test15() {422 if (test_number > 0 && test_number != 15) return;423 if (!LockType::supports_read_lock()) return;424 fprintf(stderr, "Starting Test15: recursive rlock\n");425 // DISABLEDCHECK-RD: Starting Test15426 Init(5);427 RL(0); RL(0); RU(0); RU(0); // Recusrive reader lock.428 RL(0); RL(0); RL(0); RU(0); RU(0); RU(0); // Recusrive reader lock.429 }430 431 // More detailed output test.432 void Test16() {433 if (test_number > 0 && test_number != 16) return;434 fprintf(stderr, "Starting Test16: detailed output test with two locks\n");435 // CHECK: Starting Test16436 // CHECK: WARNING: ThreadSanitizer: lock-order-inversion437 // CHECK: acquired here while holding mutex438 // CHECK: LockTest::Acquire1439 // CHECK-NEXT: LockTest::Acquire_0_then_1440 // CHECK-SECOND: previously acquired by the same thread here441 // CHECK-SECOND: LockTest::Acquire0442 // CHECK-SECOND-NEXT: LockTest::Acquire_0_then_1443 // CHECK: acquired here while holding mutex444 // CHECK: LockTest::Acquire0445 // CHECK-NEXT: LockTest::Acquire_1_then_0446 // CHECK-SECOND: previously acquired by the same thread here447 // CHECK-SECOND: LockTest::Acquire1448 // CHECK-SECOND-NEXT: LockTest::Acquire_1_then_0449 Init(5);450 Acquire_0_then_1();451 U(0); U(1);452 Acquire_1_then_0();453 U(0); U(1);454 }455 456 // More detailed output test.457 void Test17() {458 if (test_number > 0 && test_number != 17) return;459 fprintf(stderr, "Starting Test17: detailed output test with three locks\n");460 // CHECK: Starting Test17461 // CHECK: WARNING: ThreadSanitizer: lock-order-inversion462 // CHECK: LockTest::Acquire1463 // CHECK-NEXT: LockTest::Acquire_0_then_1464 // CHECK: LockTest::Acquire2465 // CHECK-NEXT: LockTest::Acquire_1_then_2466 // CHECK: LockTest::Acquire0467 // CHECK-NEXT: LockTest::Acquire_2_then_0468 Init(5);469 Acquire_0_then_1();470 U(0); U(1);471 Acquire_1_then_2();472 U(1); U(2);473 Acquire_2_then_0();474 U(0); U(2);475 }476 477 __attribute__((noinline)) void Acquire2() { L(2); }478 __attribute__((noinline)) void Acquire1() { L(1); }479 __attribute__((noinline)) void Acquire0() { L(0); }480 __attribute__((noinline)) void Acquire_1_then_0() { Acquire1(); Acquire0(); }481 __attribute__((noinline)) void Acquire_0_then_1() { Acquire0(); Acquire1(); }482 __attribute__((noinline)) void Acquire_1_then_2() { Acquire1(); Acquire2(); }483 __attribute__((noinline)) void Acquire_2_then_0() { Acquire2(); Acquire0(); }484 485 // This test creates, locks, unlocks and destroys lots of mutexes.486 void Test18() {487 if (test_number > 0 && test_number != 18) return;488 fprintf(stderr, "Starting Test18: create, lock and destroy 4 locks; all in "489 "4 threads in a loop\n");490 RunThreads(&LockTest::Test18_Thread, &LockTest::Test18_Thread,491 &LockTest::Test18_Thread, &LockTest::Test18_Thread);492 }493 494 void Test18_Thread() {495 LockType *l = new LockType[4];496 for (size_t i = 0; i < iter_count / 100; i++) {497 for (int i = 0; i < 4; i++) l[i].lock();498 for (int i = 0; i < 4; i++) l[i].unlock();499 for (int i = 0; i < 4; i++) l[i].~LockType();500 for (int i = 0; i < 4; i++) new ((void*)&l[i]) LockType();501 }502 delete [] l;503 }504 505 void Test19() {506 if (test_number > 0 && test_number != 19) return;507 fprintf(stderr, "Starting Test19: lots of lock inversions\n");508 const int kNumLocks = 45;509 Init(kNumLocks);510 for (int i = 0; i < kNumLocks; i++) {511 for (int j = 0; j < kNumLocks; j++)512 L((i + j) % kNumLocks);513 for (int j = 0; j < kNumLocks; j++)514 U((i + j) % kNumLocks);515 }516 }517 518 private:519 void Lock2(size_t l1, size_t l2) { L(l1); L(l2); U(l2); U(l1); }520 521 template<bool wait = false>522 void Lock_0_1() {523 Lock2(0, 1);524 if (wait)525 barrier_wait(&barrier);526 }527 528 template<bool wait = false>529 void Lock_1_0() {530 if (wait)531 barrier_wait(&barrier);532 Lock2(1, 0);533 }534 535 void Lock1_Loop(size_t i, size_t n_iter) {536 for (size_t it = 0; it < n_iter; it++) {537 // if ((it & (it - 1)) == 0) fprintf(stderr, "%zd", i);538 L(i);539 U(i);540 }541 // fprintf(stderr, "\n");542 }543 void Lock1_Loop_0() { Lock1_Loop(0, iter_count); }544 void Lock1_Loop_1() { Lock1_Loop(10, iter_count); }545 void Lock1_Loop_2() { Lock1_Loop(20, iter_count); }546 547 void CreateAndDestroyManyLocks() {548 LockType *create_many_locks_but_never_acquire =549 new LockType[kDeadlockGraphSize];550 (void)create_many_locks_but_never_acquire;551 delete [] create_many_locks_but_never_acquire;552 }553 554 void CreateAndDestroyLocksLoop() {555 for (size_t it = 0; it <= iter_count; it++) {556 LockType some_locks[10];557 (void)some_locks;558 }559 }560 561 void CreateLockUnlockAndDestroyManyLocks() {562 LockType many_locks[kDeadlockGraphSize];563 for (size_t i = 0; i < kDeadlockGraphSize; i++) {564 many_locks[i].lock();565 many_locks[i].unlock();566 }567 }568 569 // LockTest Member function callback.570 struct CB {571 void (LockTest::*f)();572 LockTest *lt;573 };574 575 // Thread function with CB.576 static void *Thread(void *param) {577 CB *cb = (CB*)param;578 (cb->lt->*cb->f)();579 return NULL;580 }581 582 void RunThreads(void (LockTest::*f1)(), void (LockTest::*f2)(),583 void (LockTest::*f3)() = 0, void (LockTest::*f4)() = 0) {584 const int kNumThreads = 4;585 pthread_t t[kNumThreads];586 CB cb[kNumThreads] = {{f1, this}, {f2, this}, {f3, this}, {f4, this}};587 for (int i = 0; i < kNumThreads && cb[i].f; i++)588 pthread_create(&t[i], 0, Thread, &cb[i]);589 for (int i = 0; i < kNumThreads && cb[i].f; i++)590 pthread_join(t[i], 0);591 }592 593 static const size_t kDeadlockGraphSize = 4096;594 size_t n_;595 LockType **locks_;596};597 598int main(int argc, char **argv) {599 barrier_init(&barrier, 2);600 if (argc > 1)601 test_number = atoi(argv[1]);602 if (argc > 2)603 iter_count = atoi(argv[2]);604 LockTest().Test1();605 LockTest().Test2();606 LockTest().Test3();607 LockTest().Test4();608 LockTest().Test5();609 LockTest().Test6();610 LockTest().Test7();611 LockTest().Test8();612 LockTest().Test9();613 LockTest().Test10();614 LockTest().Test11();615 LockTest().Test12();616 LockTest().Test13();617 LockTest().Test14();618 LockTest().Test15();619 LockTest().Test16();620 LockTest().Test17();621 LockTest().Test18();622 LockTest().Test19();623 fprintf(stderr, "ALL-DONE\n");624 // CHECK: ALL-DONE625}626