Problem summary:
My laptop's bluetooth randomly cuts out while I'm using it, and after that it states "No bluetooth found; plug in a dongle to use bluetooth".

Q: could it be the hardware?
I am pretty sure that it's not a hardware issue as this hasn't happened before in Windows (I dual-boot ubuntu and windows).

Q: Does bluetooth actually work?
Restarting the computer usually restores bluetooth, and I'm able to connect and use my bluetooth mouse, although it'll usually cut out a short time afterwards.

Computer info

My computer is an HP Spectre x360 Convertible 15-bl1XX (Z4Z38UA#ABA) and full product information is listed below.

Output of sudo lshw | grep product

product: HP Spectre x360 Convertible 15-bl1XX (Z4Z38UA#ABA)
 product: 827F
 product: HP26D4S9S8MH-8
 product: HP26D4S9S8MH-8
 product: Intel(R) Core(TM) i7-8550U CPU @ 1.80GHz
 product: Intel Corporation
 product: Intel Corporation
 product: Skylake Processor Thermal Subsystem
 product: Intel Corporation
 product: Sunrise Point-LP USB 3.0 xHCI Controller
 product: Sunrise Point-LP Thermal subsystem
 product: Sunrise Point-LP Serial IO I2C Controller #0
 product: Sunrise Point-LP CSME HECI #1
 product: Intel Corporation
 product: NVIDIA Corporation
 product: Sunrise Point-LP PCI Express Root Port #5
 product: Sunrise Point-LP PCI Express Root Port #7
 product: Wireless 8265 / 8275
 product: Sunrise Point-LP PCI Express Root Port #8
 product: RTS525A PCI Express Card Reader
 product: Sunrise Point-LP PCI Express Root Port #9
 product: NVMe SSD Controller SM961/PM961
 product: Intel Corporation
 product: Sunrise Point-LP PMC
 product: Intel Corporation
 product: Sunrise Point-LP SMBus
 product: KB06079XL

Output of lscpu

Architecture: x86_64
CPU op-mode(s): 32-bit, 64-bit
Byte Order: Little Endian
CPU(s): 8
On-line CPU(s) list: 0-7
Thread(s) per core: 2
Core(s) per socket: 4
Socket(s): 1
NUMA node(s): 1
Vendor ID: GenuineIntel
CPU family: 6
Model: 142
Model name: Intel(R) Core(TM) i7-8550U CPU @ 1.80GHz
Stepping: 10
CPU MHz: 800.052
CPU max MHz: 4000.0000
CPU min MHz: 400.0000
BogoMIPS: 3984.00
Virtualization: VT-x
L1d cache: 32K
L1i cache: 32K
L2 cache: 256K
L3 cache: 8192K
NUMA node0 CPU(s): 0-7
Flags: fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge mca cmov pat pse36 clflush dts acpi mmx fxsr sse sse2 ss ht tm pbe syscall nx pdpe1gb rdtscp lm constant_tsc art arch_perfmon pebs bts rep_good nopl xtopology nonstop_tsc cpuid aperfmperf tsc_known_freq pni pclmulqdq dtes64 monitor ds_cpl vmx est tm2 ssse3 sdbg fma cx16 xtpr pdcm pcid sse4_1 sse4_2 x2apic movbe popcnt tsc_deadline_timer aes xsave avx f16c rdrand lahf_lm abm 3dnowprefetch cpuid_fault epb invpcid_single pti tpr_shadow vnmi flexpriority ept vpid fsgsbase tsc_adjust bmi1 avx2 smep bmi2 erms invpcid mpx rdseed adx smap clflushopt intel_pt xsaveopt xsavec xgetbv1 xsaves dtherm ida arat pln pts hwp hwp_notify hwp_act_window hwp_epp

Output of lspci -knn | grep Net -A3; lsusb

3b:00.0 Network controller [0280]: Intel Corporation Wireless 8265 / 8275 
[8086:24fd] (rev 78)
 Subsystem: Intel Corporation Wireless 8265 / 8275 [8086:1010]
 Kernel driver in use: iwlwifi
 Kernel modules: iwlwifi
Bus 002 Device 001: ID 1d6b:0003 Linux Foundation 3.0 root hub
Bus 001 Device 003: ID 8087:0a2b Intel Corp. 
Bus 001 Device 002: ID 064e:3401 Suyin Corp. 
Bus 001 Device 001: ID 1d6b:0002 Linux Foundation 2.0 root hub

I'm currently running Ubuntu 18.04.

Install the linux-oem Kernel

sudo apt install -y linux-oem

On 20 July 2018, linux-oem version 4.15.0-1012.15 was published to the bionic-security and bionic-updates repo. It included these changes from version 4.15.0-1010.13:

 * xhci hangs; reset results in NULL pointer dereference (LP: #1763594)
 - xhci: Create new structures to store xhci port information
 - xhci: set hcd pointers for xhci usb2 and usb3 roothub structures
 - xhci: Add helper to get xhci roothub from hcd
 - xhci: xhci-hub: use new port structures to get port address instead of port
 array
 - xhci: xhci-hub: use new port structures for cas and wake mask functions.
 - xhci: xhci-ring: use port structures for port event handler
 - xhci: rename faked_port_index to hcd_portnum
 - xhci: change xhci_set_link_state() to work with port structures
 - xhci: change xhci_test_and_clear_bit() to use new port structure
 - xhci: use port structures instead of port arrays in xhci.c functions
 - xhci: xhci-hub: use port structure members instead of xhci_get_ports()
 - xhci-mtk: use xhci hub structures to get number of ports in roothubs
 - xhci: xhci-mem: remove port_arrays and the code initializing them
 - xhci: debugfs: add usb ports to xhci debugfs
 - xhci: debugfs: add debugfs interface to enable compliance mode for a port
 - xhci: Fix perceived dead host due to runtime suspend race with event handler

The last patch in that list should fix the problem of Bluetooth randomly cutting out (as well as the camera and fingerprint scanner, if you have those).

The xHCI bugfix hasn't been applied to the main kernel yet at the time of writing, so linux-oem is the only packaged Ubuntu kernel release that has the fix.

For tracking information on this bug, see the "Resources" section at the bottom of this answer.

Hack: Restore Bluetooth without Rebooting

If you would rather wait for a fix to be backported to the generic Ubuntu kernel, you can run this hack whenever Bluetooth cuts out.

Your laptop's camera, fingerprint reader, and Bluetooth controller will quickly reconnect after running these two commands:

echo 1 | sudo tee /sys/bus/pci/devices/0000:00:14.0/remove
echo 1 | sudo tee /sys/bus/pci/rescan

Note: Make sure that 0000:00:14.0 is actually the xHCI controller before running the first command. You can find the slot with this command: lspci -k | grep -B2 xhci

Explanation

This is a Band-Aid and does not fix the root cause. For bug tracking and external discussion, see the "Resources" section at the bottom of this answer.

Here's how the bug runs:

Problem Start

A bug in the xhci_hcd driver convinces it that the xHCI host controller stopped responding. As a result, it disconnects all the devices connected to the controller:

Jul 25 09:07:31 host kernel: [121258.765591] xhci_hcd 0000:00:14.0: xHC is not running.
Jul 25 09:07:31 host kernel: [121258.772300] xhci_hcd 0000:00:14.0: xHCI host controller not responding, assume dead
Jul 25 09:07:31 host kernel: [121258.772319] xhci_hcd 0000:00:14.0: HC died; cleaning up
Jul 25 09:07:31 host kernel: [121258.806828] usb 1-7: USB disconnect, device number 2
Jul 25 09:07:31 host kernel: [121258.807915] usb 1-8: USB disconnect, device number 3
Jul 25 09:07:31 host kernel: [121258.808717] usb 1-12: USB disconnect, device number 5
Jul 25 09:07:31 host upowerd[6035]: unhandled action 'unbind' on /sys/devices/pci0000:00/0000:00:14.0/usb1/1-7/1-7:1.1
Jul 25 09:07:31 host upowerd[6035]: unhandled action 'unbind' on /sys/devices/pci0000:00/0000:00:14.0/usb1/1-8
Jul 25 09:07:31 host upowerd[6035]: unhandled action 'unbind' on /sys/devices/pci0000:00/0000:00:14.0/usb1/1-7/1-7:1.0
Jul 25 09:07:31 host upowerd[6035]: unhandled action 'unbind' on /sys/devices/pci0000:00/0000:00:14.0/usb1/1-7
Jul 25 09:07:31 host upowerd[6035]: unhandled action 'unbind' on /sys/devices/pci0000:00/0000:00:14.0/usb1/1-12/1-12:1.0/bluetooth/hci0/hci0:256/0005:0A5C:4503.001E
Jul 25 09:07:31 host systemd[1]: bluetooth.target: Unit not needed anymore. Stopping.
Jul 25 09:07:31 host systemd[1]: Stopped target Bluetooth.
Jul 25 09:07:31 host upowerd[6035]: unhandled action 'unbind' on /sys/devices/pci0000:00/0000:00:14.0/usb1/1-12/1-12:1.1
Jul 25 09:07:31 host bluetoothd[12402]: Endpoint unregistered: sender=:1.61 path=/MediaEndpoint/A2DPSource
Jul 25 09:07:31 host bluetoothd[12402]: Endpoint unregistered: sender=:1.61 path=/MediaEndpoint/A2DPSink
Jul 25 09:07:31 host upowerd[6035]: unhandled action 'unbind' on /sys/devices/pci0000:00/0000:00:14.0/usb1/1-12/1-12:1.0
Jul 25 09:07:31 host upowerd[6035]: unhandled action 'unbind' on /sys/devices/pci0000:00/0000:00:14.0/usb1/1-12
Jul 25 09:07:31 host NetworkManager[4095]: <info> [1532527651.6587] bluez5: NAP: removed interface 28:16:AD:2B:5C:40

^{_{(From /var/log/syslog)}}

Removal of xHCI Controller

Running echo 1 | sudo tee /sys/bus/pci/devices/0000:00:14.0/remove hot-removes the xHCI controller PCI device:

Jul 25 09:09:57 host kernel: [121405.007193] xhci_hcd 0000:00:14.0: remove, state 4
Jul 25 09:09:57 host kernel: [121405.007208] usb usb2: USB disconnect, device number 1
Jul 25 09:09:57 host kernel: [121405.008109] xhci_hcd 0000:00:14.0: USB bus 2 deregistered
Jul 25 09:09:57 host kernel: [121405.008215] xhci_hcd 0000:00:14.0: remove, state 4
Jul 25 09:09:57 host kernel: [121405.008226] usb usb1: USB disconnect, device number 1
Jul 25 09:09:57 host kernel: [121405.010736] xhci_hcd 0000:00:14.0: USB bus 1 deregistered
Jul 25 09:09:57 host upowerd[6035]: unhandled action 'unbind' on /sys/devices/pci0000:00/0000:00:14.0/usb2/2-0:1.0
Jul 25 09:09:57 host upowerd[6035]: unhandled action 'unbind' on /sys/devices/pci0000:00/0000:00:14.0/usb1/1-0:1.0
Jul 25 09:09:57 host upowerd[6035]: unhandled action 'unbind' on /sys/devices/pci0000:00/0000:00:14.0/usb2
Jul 25 09:09:57 host upowerd[6035]: unhandled action 'unbind' on /sys/devices/pci0000:00/0000:00:14.0/usb1

^{_{(From /var/log/syslog)}}

Restoring the xHCI Controller

Running echo 1 | sudo tee /sys/bus/pci/rescan rediscovers the PCI device we just removed. The xhci_hcd driver sees the rediscovered PCI device as a new USB bus and sets up the bus and its devices:

Jul 25 09:10:11 host kernel: [121418.409659] pci 0000:00:14.0: [8086:a12f] type 00 class 0x0c0330
Jul 25 09:10:11 host kernel: [121418.409686] pci 0000:00:14.0: reg 0x10: [mem 0x3e820000-0x3e82ffff 64bit]
Jul 25 09:10:11 host kernel: [121418.409773] pci 0000:00:14.0: PME# supported from D3hot D3cold
Jul 25 09:10:11 host kernel: [121418.428182] pci 0000:00:14.0: BAR 0: assigned [mem 0x3e820000-0x3e82ffff 64bit]
Jul 25 09:10:11 host kernel: [121418.428928] xhci_hcd 0000:00:14.0: xHCI Host Controller
Jul 25 09:10:11 host kernel: [121418.428936] xhci_hcd 0000:00:14.0: new USB bus registered, assigned bus number 1
Jul 25 09:10:11 host kernel: [121418.430031] xhci_hcd 0000:00:14.0: hcc params 0x200077c1 hci version 0x100 quirks 0x00109810
Jul 25 09:10:11 host kernel: [121418.430037] xhci_hcd 0000:00:14.0: cache line size of 128 is not supported
Jul 25 09:10:11 host kernel: [121418.430401] usb usb1: New USB device found, idVendor=1d6b, idProduct=0002
Jul 25 09:10:11 host kernel: [121418.430404] usb usb1: New USB device strings: Mfr=3, Product=2, SerialNumber=1
Jul 25 09:10:11 host kernel: [121418.430407] usb usb1: Product: xHCI Host Controller
Jul 25 09:10:11 host kernel: [121418.430410] usb usb1: Manufacturer: Linux 4.15.0-29-generic xhci-hcd
Jul 25 09:10:11 host kernel: [121418.430412] usb usb1: SerialNumber: 0000:00:14.0
Jul 25 09:10:11 host kernel: [121418.430671] hub 1-0:1.0: USB hub found
Jul 25 09:10:11 host kernel: [121418.430725] hub 1-0:1.0: 16 ports detected
Jul 25 09:10:11 host kernel: [121418.432783] xhci_hcd 0000:00:14.0: xHCI Host Controller
Jul 25 09:10:11 host kernel: [121418.432792] xhci_hcd 0000:00:14.0: new USB bus registered, assigned bus number 2
Jul 25 09:10:11 host kernel: [121418.433063] usb usb2: New USB device found, idVendor=1d6b, idProduct=0003
Jul 25 09:10:11 host kernel: [121418.433067] usb usb2: New USB device strings: Mfr=3, Product=2, SerialNumber=1
Jul 25 09:10:11 host kernel: [121418.433070] usb usb2: Product: xHCI Host Controller
Jul 25 09:10:11 host kernel: [121418.433076] usb usb2: Manufacturer: Linux 4.15.0-29-generic xhci-hcd
Jul 25 09:10:11 host kernel: [121418.433078] usb usb2: SerialNumber: 0000:00:14.0
Jul 25 09:10:11 host kernel: [121418.436200] hub 2-0:1.0: USB hub found
Jul 25 09:10:11 host kernel: [121418.436223] hub 2-0:1.0: 10 ports detected
Jul 25 09:10:11 host kernel: [121418.771883] usb 1-7: new high-speed USB device number 2 using xhci_hcd
Jul 25 09:10:11 host kernel: [121418.949715] usb 1-7: New USB device found, idVendor=04ca, idProduct=7053
Jul 25 09:10:11 host kernel: [121418.949721] usb 1-7: New USB device strings: Mfr=3, Product=1, SerialNumber=2
Jul 25 09:10:11 host kernel: [121418.949725] usb 1-7: Product: HP HD Camera
Jul 25 09:10:11 host kernel: [121418.949729] usb 1-7: Manufacturer: DETNQ019I53FY0
Jul 25 09:10:11 host kernel: [121418.949732] usb 1-7: SerialNumber: 200901010001
Jul 25 09:10:11 host kernel: [121418.958393] uvcvideo: Found UVC 1.00 device HP HD Camera (04ca:7053)
Jul 25 09:10:11 host kernel: [121418.961311] uvcvideo 1-7:1.0: Entity type for entity Extension 4 was not initialized!
Jul 25 09:10:11 host kernel: [121418.961319] uvcvideo 1-7:1.0: Entity type for entity Processing 2 was not initialized!
Jul 25 09:10:11 host kernel: [121418.961324] uvcvideo 1-7:1.0: Entity type for entity Camera 1 was not initialized!
Jul 25 09:10:11 host kernel: [121418.962085] input: HP HD Camera: HP HD Camera as /devices/pci0000:00/0000:00:14.0/usb1/1-7/1-7:1.0/input/input59
Jul 25 09:10:11 host upowerd[6035]: unhandled action 'bind' on /sys/devices/pci0000:00/0000:00:14.0/usb2/2-0:1.0
Jul 25 09:10:11 host upowerd[6035]: unhandled action 'bind' on /sys/devices/pci0000:00/0000:00:14.0/usb2
Jul 25 09:10:11 host upowerd[6035]: unhandled action 'bind' on /sys/devices/pci0000:00/0000:00:14.0/usb1/1-0:1.0
Jul 25 09:10:11 host kernel: [121419.091967] usb 1-8: new full-speed USB device number 3 using xhci_hcd
Jul 25 09:10:11 host kernel: [121419.241717] usb 1-8: New USB device found, idVendor=138a, idProduct=003f
Jul 25 09:10:11 host kernel: [121419.241723] usb 1-8: New USB device strings: Mfr=0, Product=0, SerialNumber=1
Jul 25 09:10:11 host kernel: [121419.241727] usb 1-8: SerialNumber: 00b080f6fa9d
Jul 25 09:10:12 host kernel: [121419.371938] usb 1-12: new full-speed USB device number 4 using xhci_hcd
Jul 25 09:10:12 host kernel: [121419.529258] usb 1-12: New USB device found, idVendor=8087, idProduct=0a2b
Jul 25 09:10:12 host kernel: [121419.529263] usb 1-12: New USB device strings: Mfr=0, Product=0, SerialNumber=0
Jul 25 09:10:12 host upowerd[6035]: unhandled action 'bind' on /sys/devices/pci0000:00/0000:00:14.0/usb1
Jul 25 09:10:12 host kernel: [121419.537804] Bluetooth: hci0: Firmware revision 0.0 build 176 week 45 2017
Jul 25 09:10:12 host mtp-probe: checking bus 1, device 2: "/sys/devices/pci0000:00/0000:00:14.0/usb1/1-7"
Jul 25 09:10:12 host mtp-probe: checking bus 1, device 3: "/sys/devices/pci0000:00/0000:00:14.0/usb1/1-8"
Jul 25 09:10:12 host mtp-probe: bus: 1, device: 2 was not an MTP device
Jul 25 09:10:12 host mtp-probe: bus: 1, device: 3 was not an MTP device
Jul 25 09:10:12 host kernel: [121419.589011] Bluetooth: hci0: Hardware error 0x0c
Jul 25 09:10:12 host NetworkManager[4095]: <info> [1532527812.3141] bluez5: NAP: added interface 28:16:AD:2B:5C:40
Jul 25 09:10:12 host kernel: [121419.598737] Bluetooth: hci0: last event is not cmd complete (0x0f)
Jul 25 09:10:12 host kernel: [121419.598745] Bluetooth: hci0: Retrieving Intel exception info failed (-16)
Jul 25 09:10:12 host bluetoothd[12402]: Endpoint registered: sender=:1.61 path=/MediaEndpoint/A2DPSource
Jul 25 09:10:12 host bluetoothd[12402]: Endpoint registered: sender=:1.61 path=/MediaEndpoint/A2DPSink
Jul 25 09:10:12 host systemd[1]: Reached target Bluetooth.
Jul 25 09:10:12 host upowerd[6035]: unhandled action 'bind' on /sys/devices/pci0000:00/0000:00:14.0/usb1/1-8
Jul 25 09:10:12 host upowerd[6035]: unhandled action 'bind' on /sys/devices/pci0000:00/0000:00:14.0/usb1/1-7/1-7:1.1
Jul 25 09:10:12 host upowerd[6035]: unhandled action 'bind' on /sys/devices/pci0000:00/0000:00:14.0/usb1/1-12/1-12:1.1
Jul 25 09:10:12 host upowerd[6035]: unhandled action 'bind' on /sys/devices/pci0000:00/0000:00:14.0/usb1/1-12/1-12:1.0
Jul 25 09:10:12 host upowerd[6035]: unhandled action 'bind' on /sys/devices/pci0000:00/0000:00:14.0/usb1/1-12
Jul 25 09:10:12 host upowerd[6035]: unhandled action 'bind' on /sys/devices/pci0000:00/0000:00:14.0/usb1/1-7/1-7:1.0
Jul 25 09:10:12 host upowerd[6035]: unhandled action 'bind' on /sys/devices/pci0000:00/0000:00:14.0/usb1/1-7

^{_{(From /var/log/syslog)}}

As a result, the xhci_hcd driver rediscovers the attached camera, fingerprint reader, and Bluetooth controller.

Resources

• 
  Ubuntu bug report
  
  ^{― Fix released}
  xhci hangs; reset results in NULL pointer dereference
  


• 
  Debian bug report
  
  ^{― Last updated 2016-08-25}
  Keyboard/Mouse devices are disconnecting after some time or event (capslock, ) - unknown main item tag 0x0
  


• 
  Kernel bug report
  
  ^{― Assignee said bug was off-topic}
  Enabling USB (auto)suspend (power control) for xHCI controllers incurs random device failures since kernel 4.15
  


• 
  Ubuntu kernel patchset
  
  ^{― Proposed fix has not been backported yet}
  Fix "xHCI host controller not responding, assume dead"
  


• 
  Arch Linux Forums discussion
  
  ^{― Bug affects forum users}
  xHCI host controller not responding, assume dead
  

Tip: use && if your keyboard will be in that controller to avoid get halted before typing the second command...

echo 1 | sudo tee /sys/bus/pci/devices/0000:00:14.0/remove && echo 1 | sudo tee /sys/bus/pci/rescan